今天继续算法学习，本次学习的是高级排序之快速排序。本文代码部分存在调用公共方法，可在文章：简单排序算法之冒泡、插入和选择排序-JAVA实现版 ，高级排序之归并排序、希尔排序。中查找相关方法，另外，本文也提供测试时使用的完整代码，对其他算法不感兴趣，可在文末找到完整源代码。
快速排序的本质就是把一个数组划分为两个子数组，然后递归地调用自身为每一个数组进行“快速排序”来实现的。这里就涉及一个问题：如何划分？
在快速排序中，为了划分数组，提出了“枢纽”这个词，它代表待排序序列中的一个数据项。快速排序利用枢纽将数组划分成两部分，一部分（枢纽左侧）是所有小于该枢纽表示的数据项，另一部分（枢纽右侧）则都大于该枢纽表示的数据项（注意，此时左右两侧的数据项是无序的），枢纽放置在左右两侧的中间，此时该枢纽已经处在排序的正确位置上了（枢纽是快速排序所排序的对象，实现“排序”的关键点就是调整枢纽的位置）。通过递归的这样划分，最终出现左侧只有一个数据项（该数据项既是左侧子数组又是枢纽），则结束左侧递归，开始划分右侧数组。。。以此类推。这里又产生了一个问题，如何选择枢纽？
选择枢纽的算法：最简单的选择枢纽算法就是每次递归都选择数组的最后一个数据项做为枢纽（或者选择最左侧的数据项作枢纽）。
上图演示了以子数组最右侧数据项做枢纽的排序过程
private static int partitionIt(int left,int right,int pivot,int[] array){ int leftPtr = left-1; int rightPtr = right; while(true){ // 查找左侧子数组大于枢纽的位置 while(compare(array[++leftPtr],pivot)<0){ } // 查询右侧子数组小于枢纽的位置 while(rightPtr>0&&compare(array[--rightPtr],pivot)>0){ } if(leftPtr>=rightPtr){ break; } // 交换需要调整位置的两个数据项 swap(leftPtr,rightPtr,array); } // 将枢纽挪到两侧中间 swap(leftPtr,right,array); return leftPtr; } private static void recQuickSort(int left,int right,int[] array){ if(right-left<=0){ return; } // 选择的枢纽 int pivot = array[right]; int partition = partitionIt(left,right,pivot,array); recQuickSort(left,partition-1,array); recQuickSort(partition+1,right,array); } public static void quickSort(int[] array){ compareCount=0; swapCount=0; long start = new Date().getTime(); recQuickSort(0,array.length-1,array); long end = new Date().getTime(); printResult("快速排序","交换次数",start,end); }
冒泡排序——比较次数:49995000,交换次数:25153125,耗时:173毫秒
选择排序——比较次数:49995000,交换次数:9987,耗时:65毫秒
插入排序——比较次数:25075792,复制次数:25075793,耗时:42毫秒
归并排序——比较次数:120459,复制次数:267232,耗时:3毫秒
希尔排序——比较次数:233896,复制次数:238266,耗时:5毫秒
对随机序列排序：快速排序——比较次数:165181,交换次数:31700,耗时:3毫秒
对逆序序列排序：快速排序——比较次数:49825881,交换次数:9976,耗时:54毫秒
从运行结果中，可以看到对于随机序列，快速排序算法执行速度是非常快的，和归并排序相同，但给逆序序列排序时，效果则非常差，几乎和选择排序一样的效率了。那这是为什么呢？
根本原因，就在于枢纽的选择上，快速排序期望枢纽能够将数组拆分成两个长度几乎相同的子数组，这样能最优的平衡比较次数和交换次数。对于随机序列，简单的选择最右侧数据项做为枢纽不至于频繁出现左右子数组极度不平衡的情况，而对于逆序序列，则几乎每次划分都是极度不平衡的两个子数组，最终导致较大侧的子数组要被划分更多次。
快速排序的最优划分结果是划分的两个数组长度相等，为了达到这个目的，我们每次都要在划分前，先找到子数组的中间数据项吗？显然，不能这么做的，因为很可能你找中值的时间远远大于你排序的时间了。所以，我们只能选择一个实现既不是过于复杂，又比“选择最右侧数据项做为枢纽”的算法更具普适性。
上图所示取枢纽的方法叫“三数据项取中”，即从数组中选择第一个、最后一个以及中间的数据项，从这三个数据项中取出大小在中间的项做为枢纽，在选择过程中，我们实际上也对这三个数据项做了排序，那顺便把分别大于、小于枢纽的那两个数据项也放到正确的位置（即左侧小于枢纽，右侧大于枢纽）。
该方法每次划分都需要至少有三个数据项，所以当子数组项数不大于3个的时候，就可以结束递归划分了，此时的排序可以通过其他排序算法实现，如使用手动排序（待排序的数据项不大于3个，所以手动排序完全可以轻松搞定），也可以使用插入排序（如果使用插入排序，我们甚至可以当数据项不大于10（这个10没有具体意义，你也可以20、30）的时候就可以用插入排序来收尾了）。下面我们用该方法来选择枢纽（用插入排序来收尾），对代码进行修改。
private static int medianOf3(int left,int right,int[] array){ int center = (left+right)/2; if(array[left]>array[center]){ swap(left,center,array); } if(array[left]>array[right]){ swap(left,right,array); } if(array[center]>array[right]){ swap(center,right,array); } swap(center,right-1,array); return array[right-1]; } private static void insertSort(int left,int right,int[] array){ for (int i = left+1; i <= right; i++) { int temp = array[i]; int cur = i; // 右移数字，实现cur下标的左侧都是有序的 while (cur > 0 && compare(temp, array[cur - 1]) < 0) { copy(cur-1,cur,array); cur--; } // 如果cur==i则说明数据项已经在正确的位置了，不需要进行交换 if (cur != i) { // 不满足temp<array[cur-1]时，则当前正在排的项temp已经找到正确位置了 copyData(temp,cur,array); } } } private static int partitionIt(int left,int right,int pivot,int[] array){ int leftPtr = left; int rightPtr = right-1; while(true){ // 查找左侧子数组大于枢纽的位置 while(compare(array[++leftPtr],pivot)<0){ } // 查询右侧子数组小于枢纽的位置 while(compare(array[--rightPtr],pivot)>0){ } if(leftPtr>=rightPtr){ break; } // 交换需要调整位置的两个数据项 swap(leftPtr,rightPtr,array); } // 将枢纽挪到两侧中间 swap(leftPtr,right-1,array); return leftPtr; } private static void recQuickSort(int left,int right,int[] array){ int size = right-left+1; if(size <10){ insertSort(left,right,array); }else{ int median = medianOf3(left,right,array); int partition = partitionIt(left,right,median,array); recQuickSort(left,partition-1,array); recQuickSort(partition+1,right,array); } } public static void quickSort(int[] array){ compareCount=0; swapCount=0; long start = new Date().getTime(); recQuickSort(0,array.length-1,array); long end = new Date().getTime(); printResult("快速排序","交换次数",start,end); }
冒泡排序——比较次数:49995000,交换次数:25138570,耗时:170毫秒
选择排序——比较次数:49995000,交换次数:9990,耗时:65毫秒
插入排序——比较次数:25069178,复制次数:25069176,耗时:34毫秒
归并排序——比较次数:120483,复制次数:267232,耗时:2毫秒
希尔排序——比较次数:231598,复制次数:235991,耗时:6毫秒
对随机序列排序：快速排序——比较次数:154857,交换次数:44570,耗时:3毫秒
对逆序序列排序：快速排序——比较次数:188034,交换次数:20067,耗时:1毫秒
从执行结果可以看出，优化过枢纽选择算法后，无论是随机序列排序还是逆序序列排序，排序速度都非常快。
至此，本文结束
package team.ngup.study;import java.util.Arrays;import java.util.Date;import java.util.concurrent.ThreadLocalRandom;/** * @author zww * @date 2022/8/4 10:35 */public class SortStudy { static final int ARRAY_SIZE = 10000; static int compareCount = 0; static int swapCount = 0; /** * 生成随机数数组 * * @return */ public static int[] buildRandomArray() { int[] array = new int[ARRAY_SIZE]; for (int i = 0; i < ARRAY_SIZE; i++) { int randomWithThreadLocalRandom = ThreadLocalRandom.current().nextInt(0, 1000000); array[i] = randomWithThreadLocalRandom; } return array; } /** * a和b位置的数据交换 * * @param a * @param b * @param array */ public static void swap(int a, int b, int[] array) { swapCount++; int temp = array[a]; array[a] = array[b]; array[b] = temp; } /** * 复制 位置 a->b * @param a * @param b * @param array */ private static void copy(int a,int b,int[] array){ swapCount++; array[b] = array[a]; } /** * 复制 数值a->位置b * @param a * @param b * @param array */ private static void copyData(int a,int b,int[] array){ swapCount++; array[b]=a; } /** * dataa大于datab返回1，否则返回-1 * * @param dataa * @param datab * @return */ public static int compare(int dataa, int datab) { compareCount++; if (dataa >= datab) { return 1; } return -1; } /** * 输出排序结果 * * @param name 排序方法名 * @param operName 交换/复制 * @param start 开始时间 * @param end 结束时间 */ private static void printResult(String name,String operName,long start,long end){ System.out.print( name + "——比较次数:" + compareCount + ","+operName+":" + swapCount + ",耗时:" + (end - start) + "毫秒"); } /** 冒泡排序 */ public static void maopao(int[] array) { compareCount = 0; swapCount = 0; // 待排序序列长度， int length = array.length; long start = new Date().getTime(); while (length > 0) { for (int a = 0; a < length - 1; a++) { if (compare(array[a], array[a + 1]) > 0) { // 交换位置 swap(a, a + 1, array); } } // 一次从头到尾的遍历，找出了最右端的值（最大值），这将缩短第二次遍历的序列长度 length--; } long end = new Date().getTime(); // 输出排序结果 printResult("冒泡排序","交换次数", start, end); } /** 选择排序 */ public static void xuanze(int[] array) { compareCount = 0; swapCount = 0; int length = 0; long start = new Date().getTime(); while (length != array.length - 1) { // 最小值位置 int minPosition = -1; // 最小值 int min = array[length]; for (int i = length + 1; i < array.length; i++) { if (compare(array[i], min) < 0) { min = array[i]; minPosition = i; } } // 存在比当前值还要小的值，则进行位置对换，否则无需对调位置 if (minPosition != -1) { // 交换位置 swap(length, minPosition, array); } length++; } long end = new Date().getTime(); printResult("选择排序","交换次数", start, end); } /** 插入排序 */ public static void charu(int[] array) { swapCount = 0; compareCount = 0; // 第一次排序无需比较，所以直接从1开始 long start = new Date().getTime(); for (int i = 1; i < array.length; i++) { int temp = array[i]; int cur = i; // 右移数字，实现cur下标的左侧都是有序的 while (cur > 0 && compare(temp, array[cur - 1]) < 0) { copy(cur-1,cur,array); cur--; } // 如果cur==i则说明数据项已经在正确的位置了，不需要进行交换 if (cur != i) { // 不满足temp<array[cur-1]时，则当前正在排的项temp已经找到正确位置了 copyData(temp,cur,array); } } long end = new Date().getTime(); printResult("插入排序" ,"复制次数", start, end); } // ------------------高级排序------------------------ private static void merge(int[] array, int[] workSpace, int lowPtr, int highPtr, int upperBound) { int j = 0; int lowerBound = lowPtr; int mid = highPtr - 1; int n = upperBound - lowerBound + 1; while (lowPtr <= mid && highPtr <= upperBound) { if (compare(array[lowPtr],array[highPtr])<0) { copyData(array[lowPtr++],j++,workSpace); } else { copyData(array[highPtr++],j++,workSpace); } } while (lowPtr <= mid) { copyData(array[lowPtr++],j++,workSpace); } while (highPtr <= upperBound) { copyData(array[highPtr++],j++,workSpace); } for (j = 0; j < n; j++) { copyData(workSpace[j],lowerBound+j,array); } } private static void recMergeSort(int[] array,int[] workSpace, int lowerBound, int upperBound) { if (lowerBound == upperBound) { return; } int mid = (lowerBound + upperBound) / 2; recMergeSort(array,workSpace, lowerBound, mid); // 分割左侧 recMergeSort(array,workSpace, mid + 1, upperBound); // 分割右侧 merge(array,workSpace,lowerBound,mid+1,upperBound); // 合并排序 } /** * 合并排序 * @param array */ public static void mergeSort(int[] array){ compareCount=0; swapCount=0; int[] workspace = new int[array.length]; long start = new Date().getTime(); recMergeSort(array,workspace,0,array.length-1); long end = new Date().getTime(); printResult("归并排序","复制次数",start,end); } /** * 希尔排序 * @param array */ public static void xierSort(int[] array){ compareCount=0; swapCount=0; int inner,outer; int temp; int h=1; // 计算跨度 while(h<=array.length/3){ h=h*3+1; } long start = new Date().getTime(); while(h>0){ for(outer=h;outer<array.length;outer++){ temp = array[outer]; inner = outer; while(inner>h-1 && compare(array[inner-h],temp)>0){ copy(inner-h,inner,array); inner -= h; } copyData(temp,inner,array); } h=(h-1)/3; } long end = new Date().getTime(); printResult("希尔排序","复制次数",start,end); } //-------------快速排序---------------------// private static int medianOf3(int left,int right,int[] array){ int center = (left+right)/2; if(compare(array[left],array[center])>0){ swap(left,center,array); } if(compare(array[left],array[right])>0){ swap(left,right,array); } if(compare(array[center],array[right])>0){ swap(center,right,array); } swap(center,right-1,array); return array[right-1]; } private static void insertSort(int left,int right,int[] array){ for (int i = left+1; i <= right; i++) { int temp = array[i]; int cur = i; // 右移数字，实现cur下标的左侧都是有序的 while (cur > 0 && compare(temp, array[cur - 1]) < 0) { copy(cur-1,cur,array); cur--; } // 如果cur==i则说明数据项已经在正确的位置了，不需要进行交换 if (cur != i) { // 不满足temp<array[cur-1]时，则当前正在排的项temp已经找到正确位置了 copyData(temp,cur,array); } } } private static int partitionIt(int left,int right,int pivot,int[] array){ int leftPtr = left; int rightPtr = right-1; while(true){ // 查找左侧子数组大于枢纽的位置 while(compare(array[++leftPtr],pivot)<0){ } // 查询右侧子数组小于枢纽的位置 while(compare(array[--rightPtr],pivot)>0){ } if(leftPtr>=rightPtr){ break; } // 交换需要调整位置的两个数据项 swap(leftPtr,rightPtr,array); } // 将枢纽挪到两侧中间 swap(leftPtr,right-1,array); return leftPtr; } private static void recQuickSort(int left,int right,int[] array){ int size = right-left+1; if(size <10){ insertSort(left,right,array); }else{ int median = medianOf3(left,right,array); int partition = partitionIt(left,right,median,array); recQuickSort(left,partition-1,array); recQuickSort(partition+1,right,array); } } public static void quickSort(int[] array){ compareCount=0; swapCount=0; long start = new Date().getTime(); recQuickSort(0,array.length-1,array); long end = new Date().getTime(); printResult("快速排序","交换次数",start,end); } public static void mAIn(String[] args) { int[] array = buildRandomArray(); int[] array2 = Arrays.copyOf(array, ARRAY_SIZE); int[] array3 = Arrays.copyOf(array, ARRAY_SIZE); int[] array4 = Arrays.copyOf(array,ARRAY_SIZE); int[] array5 = Arrays.copyOf(array,ARRAY_SIZE); int[] array6 = Arrays.copyOf(array,ARRAY_SIZE); maopao(array); System.out.println(); xuanze(array2); System.out.println(); charu(array3); System.out.println(); mergeSort(array4); System.out.println(); xierSort(array5); System.out.println(); // 随机数据项 进行快速排序 System.out.print("对随机序列排序："); quickSort(array6); System.out.println(); // 将array6逆序 int[] array6a = new int[array6.length]; for(int i=array6.length-1,j=0;i>=0;i--){ array6a[j] = array6[i]; j++; } // 对逆序的数组使用快速排序 System.out.print("对逆序序列排序："); quickSort(array6a); }}
京公网安备 11010802035086号