前言
今天繼續算法學習，本次學習的是高級排序之快速排序。本文代碼部分存在調用公共方法，可在文章：簡單排序算法之冒泡、插入和選擇排序-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); }}
