本文主要是介绍冒泡排序快速排序（前后指针、挖坑、左右指针法）【Java实现】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、冒泡排序
思想：
对N个元素进行升序排列时，依次比较两个相邻的元素，如果前者大于后者就交换，一趟排序找出一个最大值并放在最后，然后缩小排序区间继续找出该区间的最大值，并放在倒数第二个位置，倒数第一个位置...，直到区间缩小至只剩一个元素，排序完成。整个排序过程要进行N-1趟排序。
原理：
1.比较相邻的元素。如果前者比后者大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
待排序序列： 2 5 7 1 3 7
第一趟排序：
2 5 7 1 3 7 -> 2 5 7 1 3 7
2 5 7 1 3 7 -> 2 5 7 1 3 7
2 5 7 1 3 7 -> 2 5 1 7 3 7
2 5 1 7 3 7 -> 2 5 1 3 7 7
2 5 1 3 7 7 -> 2 5 1 3 7 7
第一趟排序后的序列：2 5 1 3 7 7
第二趟排序：
2 5 1 3 7 -> 2 5 1 3 7
2 5 1 3 7 -> 2 1 5 3 7
2 1 5 3 7 -> 2 1 3 5 7
2 1 3 5 7 -> 2 1 3 5 7
第二趟排序后的序列：2 1 3 5 7 7
第三趟排序：
2 1 3 5 -> 1 2 3 5
1 2 3 5 -> 1 2 3 5
1 2 3 5 -> 1 2 3 5
第三趟排序后的序列：1 2 3 5 7 7
第四趟排序：
1 2 3 -> 1 2 3
1 2 3 -> 1 2 3
第四趟排序后的序列：1 2 3 5 7 7
第五趟排序：
1 2 -> 1 2
第五趟排序后的序列：1 2 3 5 7 7
排序完成！
注意：
假如给定待排序序列已经有序，如{1,2,4,5,6,7}，那么第一次排序便不会交换相邻元素。后续比较排序也是。所以，为了减少已经有序的待排序序列的排序时间，我们可以设置一个标志位flag，初值为false。如果某一次排序过程中有交换元素，便将flag置为true。下一次排序之前又将flag置为1；如果此次排序完成flag仍为1，说明此次排序没有交换任何元素，那么证明该序列已经有序，则不需要再继续进行排序。整个排序过程就完成了。所以最多可进行n-1趟排序。
public class BubbleSort {private int[] arr;private int len;public BubbleSort(int[] arr) {this.arr = arr;this.len = arr.length;}public void bubbleSort() {for (int i = len - 1; i > 0; i--) {//len个元素，总共进行len-1趟排序boolean flag = false;//标识此趟排序是否有元素交换了位置，flag为false表示没交换for (int j = 0; j < i; j++) {//每进行完一趟排序，将要排序的区间缩小1个元素if (arr[j] > arr[j + 1]) {swap(j, j + 1);flag = true;//有元素交换，flag置为true}}//如果一趟排序下来flag一直为false，表明此趟排序没有元素交换位置，说明此时数组已经有序，可结束排序if (flag == false) {return;}}}public void swap(int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public void print() {for (int i = 0; i < len; i++) {System.out.print(arr[i] + " ");}System.out.println("");}}
稳定性判断：
因为冒泡排序是不断把大的元素往后调的过程，此过程是不断比较相邻元素并交换的过程，所以如果两个相邻元素相等的话，我们并不会交换它俩的位置；如果两个元素相等不相邻的话，就算通过交换会将两个相等元素调到相邻，此时我们也不会交换它俩的位置，所以排序前后相同元素的位置顺序并没有改变，所以冒泡排序是一个稳定的排序算法。
测试类代码如下：
package com.myself.sort;import java.util.Scanner;public class TestSort {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {int len = scanner.nextInt();int[] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = scanner.nextInt();}//冒泡排序BubbleSort sortArr = new BubbleSort(arr);sortArr.bubbleSort();sortArr.print();}}
}
二、快速排序
快速排序是对冒泡排序的一种改进。
思想：
通过选择一个基准值将要排序的数据分成两个区间，其中一个区间的所有元素都比基准值小，另一个区间的所有元素都比基准值大。然后采用分而治之的方法对这两部分数据分别进行快速排序，当区间中只剩一个数或者为空时停止此次排序，以此达到整个数据变成有序序列。
快排主要有3种实现方法：hoare法，又称左右指针法；挖坑法；前后指针法（现为了简便，下面三种方法均以区间右端点所在元素作为基准值）
左右指针法：定义两个指针begin和end，其初值分别为待排序区间左端点、右端点，begin从左往右走，寻找比基准值小或等的元素，end从右往左走，寻找比基准值大或等的元素。当begin停下时，表面此时的元素大于基准值；当end停下时，表面此时的元素小于基准值。此时交换对应的两个元素，继续上述过程。最后当begin和end相等时，交换其中一个元素和基准值，并返回基准值此时的下标。
以数组{2,9,3,6,7,5}为例，具体排序过程如下图所示
此时基准值5将区间分成两个小区间 ，一个区间内的元素都小于等于5，另一个区间内的元素都大于等于5。
左区间排序如下：
右区间排序如下：
代码实现如下：
//1. 左右指针法private int parition1(int left, int right) {int begin = left;int end = right;while (begin < end) {while ((begin < end) && (arr[begin] <= arr[right])) {//此步的begin<end一定要写，因为如果区间本身已经有序，begin会一直往右走，直到走到end，还会继续往右走begin++;}//此时begin所指向的元素比基准值大while ((begin < end) && (arr[end] >= arr[right])) {//同理，此步的begin<end也一定要写end--;}//此时end所指向的元素比基准值小swap(begin, end);//交换begin和end所指向的元素}swap(begin,right);return begin;}挖坑法：先将基准值保存起来，此时相当于基准值的位置就空出来了。然后定义两个指针begin和end，其初始值分别为待排序区间的左端点和右端点，begin寻找比基准值大的元素，end寻找比基准值小的元素。当begin找到比基准值大的元素之后，此时将其赋给end所指位置，那么begin所指位置便又空出来了；当end找到比基准值小的元素之后，此时将其赋给begin所指位置，那么此时end所指位置又空出来了。重复上述过程，直到begin==end。此时将基准值赋给begin所指位置并返回下标begin。
以{2,9,3,6,7,5}为例，具体排序过程如下
此时基准值5将区间分成了两个小区间，其中左区间的元素全部小于等于5，右区间的元素全部大于等于5
其中左区间排序如下：
右区间排序如下：
代码实现如下：
//2. 挖坑法private int parition2(int left, int right) {int key = arr[right];//记录基准值int begin = left;int end = right;while (begin < end) {while ((begin < end) && (arr[begin] <= key)) {begin++;}//此时begin所指向的值比基准值大arr[end] = arr[begin];while ((begin < end) && (arr[end] >= key)) {end--;}arr[begin] = arr[end];}arr[begin] = key;return begin;}
前后指针法：定义两个指针div和cur，初始值均为待排序区间的左端点，其中div所指位置之前表示比基准值小或等的元素，div和cur之间表示比基准值大的元素，cur之后表示待排序部分。在cur遍历整个待排序区域期间，如果cur所指元素小于div所指元素，则交换，此时div++。最后交换div所指元素和基准值，并返回基准值此时的下标。
以数组{2,9,3,6,7,5}为例
此时5将区间分成了两个小区间，分别对两个小区间按同样的方法进行排序。
左区间排序如下所示：
右区间排序如下所示：
代码实现如下：
//3. 前后指针法private int parition3(int left, int right) {int div = left;int cur;for (cur = left; cur < right; cur++) {if (arr[cur] <= arr[right]) {//遇到cur指向的值小于等于基准值就交换div和cur指向的值，并让div往右走一步，以保证div之前的值都小于等于基准值swap(div, cur);div++;}}//此时cur=rightswap(div, cur);return div;}
快速排序三种方法完整代码如下：
public class QuickSort {private int[] arr;private int len;public QuickSort(int[] arr) {this.arr = arr;this.len = arr.length;}public void quickSort() {__quickSort(0, len - 1);}private void __quickSort(int left, int right) {if (left == right) {//区间只剩一个元素的情况下不用再进行排序return;}if (left > right) {//区间没有元素了return;}int div = parition3(left, right);__quickSort(left, div - 1);__quickSort(div + 1, right);}
//以下三种方法均以区间最后一个元素作为基准值//1. 左右指针法private int parition1(int left, int right) {int begin = left;int end = right;while (begin < end) {while ((begin < end) && (arr[begin] <= arr[right])) {//此步的begin<end一定要写，因为如果区间本身已经有序，begin会一直往右走，直到走到end，还会继续往右走begin++;}//此时begin所指向的元素比基准值大while ((begin < end) && (arr[end] >= arr[right])) {//同理，此步的begin<end也一定要写end--;}//此时end所指向的元素比基准值小swap(begin, end);//交换begin和end所指向的元素}swap(begin,right);return begin;}//2. 挖坑法private int parition2(int left, int right) {int key = arr[right];//记录基准值int begin = left;int end = right;while (begin < end) {while ((begin < end) && (arr[begin] <= key)) {begin++;}//此时begin所指向的值比基准值大arr[end] = arr[begin];while ((begin < end) && (arr[end] >= key)) {end--;}arr[begin] = arr[end];}arr[begin] = key;return begin;}//3. 前后指针法private int parition3(int left, int right) {int div = left;int cur;for (cur = left; cur < right; cur++) {if (arr[cur] <= arr[right]) {//遇到cur指向的值小于等于基准值就交换div和cur指向的值，并让div往右走一步，以保证div之前的值都小于等于基准值swap(div, cur);div++;}}//此时cur=rightswap(div, cur);return div;}//交换两个元素的值public void swap(int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public void print() {for (int i = 0; i < len; i++) {System.out.print(arr[i] + " ");}System.out.println("");}
}
测试类代码如下：
package com.myself.sort;import java.util.Scanner;public class TestSort {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {int len = scanner.nextInt();int[] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = scanner.nextInt();}//快速排序QuickSort quickSort=new QuickSort(arr);quickSort.quickSort();quickSort.print();}}
}
稳定性判断：
由于以上三种方法实现快速排序的基本思想都一样，现以左右指针法为例，在左右指针begin和end不断向中间靠拢的过程中，只有begin遇到大于基准值或begin等于end的时候才会停下来，同样，end在遇到小于基准值或begin==end时也会停下来，此时进行begin和end所指元素交换操作，然后继续该过程，直到begin==end。此时交换begin所指元素和基准值，而该过程很有可能会把前面元素的稳定性打乱，以{2,9,3,6,5,5}为例，交换基准值5和9的位置，会让基准值（第二个5）跑到第一个5的前面，导致排序前后相同元素的前后顺序不一致，所以快速排序是一个不稳定的排序算法。
这篇关于冒泡排序快速排序（前后指针、挖坑、左右指针法）【Java实现】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
