前言
今天繼續(xù)算法學(xué)習(xí)，本次學(xué)習(xí)的是高級排序之快速排序。本文代碼部分存在調(diào)用公共方法，可在文章：簡單排序算法之冒泡、插入和選擇排序-JAVA實現(xiàn)版 ，高級排序之歸并排序、希爾排序。中查找相關(guān)方法，另外，本文也提供測試時使用的完整代碼，對其他算法不感興趣，可在文末找到完整源代碼。
快速排序
快速排序的本質(zhì)就是把一個數(shù)組劃分為兩個子數(shù)組，然后遞歸地調(diào)用自身為每一個數(shù)組進(jìn)行“快速排序”來實現(xiàn)的。這里就涉及一個問題：如何劃分？
在快速排序中，為了劃分?jǐn)?shù)組，提出了“樞紐”這個詞，它代表待排序序列中的一個數(shù)據(jù)項。快速排序利用樞紐將數(shù)組劃分成兩部分，一部分（樞紐左側(cè)）是所有小于該樞紐表示的數(shù)據(jù)項，另一部分（樞紐右側(cè)）則都大于該樞紐表示的數(shù)據(jù)項（注意，此時左右兩側(cè)的數(shù)據(jù)項是無序的），樞紐放置在左右兩側(cè)的中間，此時該樞紐已經(jīng)處在排序的正確位置上了（樞紐是快速排序所排序的對象，實現(xiàn)“排序”的關(guān)鍵點就是調(diào)整樞紐的位置）。通過遞歸的這樣劃分，最終出現(xiàn)左側(cè)只有一個數(shù)據(jù)項（該數(shù)據(jù)項既是左側(cè)子數(shù)組又是樞紐），則結(jié)束左側(cè)遞歸，開始劃分右側(cè)數(shù)組。。。以此類推。這里又產(chǎn)生了一個問題，如何選擇樞紐？
選擇樞紐的算法：最簡單的選擇樞紐算法就是每次遞歸都選擇數(shù)組的最后一個數(shù)據(jù)項做為樞紐（或者選擇最左側(cè)的數(shù)據(jù)項作樞紐）。
上圖演示了以子數(shù)組最右側(cè)數(shù)據(jù)項做樞紐的排序過程
代碼演示（樞紐始終使用子數(shù)組的最右側(cè)數(shù)據(jù)項）
private static int partitionIt(int left,int right,int pivot,int[] array){ int leftPtr = left-1; int rightPtr = right; while(true){ // 查找左側(cè)子數(shù)組大于樞紐的位置 while(compare(array[++leftPtr],pivot)<0){ } // 查詢右側(cè)子數(shù)組小于樞紐的位置 while(rightPtr>0&&compare(array[--rightPtr],pivot)>0){ } if(leftPtr>=rightPtr){ break; } // 交換需要調(diào)整位置的兩個數(shù)據(jù)項 swap(leftPtr,rightPtr,array); } // 將樞紐挪到兩側(cè)中間 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("快速排序","交換次數(shù)",start,end); }
運行結(jié)果
冒泡排序——比較次數(shù):49995000,交換次數(shù):25153125,耗時:173毫秒
選擇排序——比較次數(shù):49995000,交換次數(shù):9987,耗時:65毫秒
插入排序——比較次數(shù):25075792,復(fù)制次數(shù):25075793,耗時:42毫秒
歸并排序——比較次數(shù):120459,復(fù)制次數(shù):267232,耗時:3毫秒
希爾排序——比較次數(shù):233896,復(fù)制次數(shù):238266,耗時:5毫秒
對隨機序列排序：快速排序——比較次數(shù):165181,交換次數(shù):31700,耗時:3毫秒
對逆序序列排序：快速排序——比較次數(shù):49825881,交換次數(shù):9976,耗時:54毫秒
從運行結(jié)果中，可以看到對于隨機序列，快速排序算法執(zhí)行速度是非?？斓?，和歸并排序相同，但給逆序序列排序時，效果則非常差，幾乎和選擇排序一樣的效率了。那這是為什么呢？
根本原因，就在于樞紐的選擇上，快速排序期望樞紐能夠?qū)?shù)組拆分成兩個長度幾乎相同的子數(shù)組，這樣能最優(yōu)的平衡比較次數(shù)和交換次數(shù)。對于隨機序列，簡單的選擇最右側(cè)數(shù)據(jù)項做為樞紐不至于頻繁出現(xiàn)左右子數(shù)組極度不平衡的情況，而對于逆序序列，則幾乎每次劃分都是極度不平衡的兩個子數(shù)組，最終導(dǎo)致較大側(cè)的子數(shù)組要被劃分更多次。
優(yōu)化樞紐選擇算法
快速排序的最優(yōu)劃分結(jié)果是劃分的兩個數(shù)組長度相等，為了達(dá)到這個目的，我們每次都要在劃分前，先找到子數(shù)組的中間數(shù)據(jù)項嗎？顯然，不能這么做的，因為很可能你找中值的時間遠(yuǎn)遠(yuǎn)大于你排序的時間了。所以，我們只能選擇一個實現(xiàn)既不是過于復(fù)雜，又比“選擇最右側(cè)數(shù)據(jù)項做為樞紐”的算法更具普適性。
上圖所示取樞紐的方法叫“三數(shù)據(jù)項取中”，即從數(shù)組中選擇第一個、最后一個以及中間的數(shù)據(jù)項，從這三個數(shù)據(jù)項中取出大小在中間的項做為樞紐，在選擇過程中，我們實際上也對這三個數(shù)據(jù)項做了排序，那順便把分別大于、小于樞紐的那兩個數(shù)據(jù)項也放到正確的位置（即左側(cè)小于樞紐，右側(cè)大于樞紐）。
該方法每次劃分都需要至少有三個數(shù)據(jù)項，所以當(dāng)子數(shù)組項數(shù)不大于3個的時候，就可以結(jié)束遞歸劃分了，此時的排序可以通過其他排序算法實現(xiàn)，如使用手動排序（待排序的數(shù)據(jù)項不大于3個，所以手動排序完全可以輕松搞定），也可以使用插入排序（如果使用插入排序，我們甚至可以當(dāng)數(shù)據(jù)項不大于10（這個10沒有具體意義，你也可以20、30）的時候就可以用插入排序來收尾了）。下面我們用該方法來選擇樞紐（用插入排序來收尾），對代碼進(jìn)行修改。
代碼演示
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; // 右移數(shù)字，實現(xiàn)cur下標(biāo)的左側(cè)都是有序的 while (cur > 0 && compare(temp, array[cur - 1]) < 0) { copy(cur-1,cur,array); cur--; } // 如果cur==i則說明數(shù)據(jù)項已經(jīng)在正確的位置了，不需要進(jìn)行交換 if (cur != i) { // 不滿足temp<array[cur-1]時，則當(dāng)前正在排的項temp已經(jīng)找到正確位置了 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){ // 查找左側(cè)子數(shù)組大于樞紐的位置 while(compare(array[++leftPtr],pivot)<0){ } // 查詢右側(cè)子數(shù)組小于樞紐的位置 while(compare(array[--rightPtr],pivot)>0){ } if(leftPtr>=rightPtr){ break; } // 交換需要調(diào)整位置的兩個數(shù)據(jù)項 swap(leftPtr,rightPtr,array); } // 將樞紐挪到兩側(cè)中間 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("快速排序","交換次數(shù)",start,end); }
運行結(jié)果
冒泡排序——比較次數(shù):49995000,交換次數(shù):25138570,耗時:170毫秒
選擇排序——比較次數(shù):49995000,交換次數(shù):9990,耗時:65毫秒
插入排序——比較次數(shù):25069178,復(fù)制次數(shù):25069176,耗時:34毫秒
歸并排序——比較次數(shù):120483,復(fù)制次數(shù):267232,耗時:2毫秒
希爾排序——比較次數(shù):231598,復(fù)制次數(shù):235991,耗時:6毫秒
對隨機序列排序：快速排序——比較次數(shù):154857,交換次數(shù):44570,耗時:3毫秒
對逆序序列排序：快速排序——比較次數(shù):188034,交換次數(shù):20067,耗時:1毫秒
從執(zhí)行結(jié)果可以看出，優(yōu)化過樞紐選擇算法后，無論是隨機序列排序還是逆序序列排序，排序速度都非?？?。
至此，本文結(jié)束
完整代碼
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; /** * 生成隨機數(shù)數(shù)組 * * @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位置的數(shù)據(jù)交換 * * @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; } /** * 復(fù)制 位置 a->b * @param a * @param b * @param array */ private static void copy(int a,int b,int[] array){ swapCount++; array[b] = array[a]; } /** * 復(fù)制 數(shù)值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; } /** * 輸出排序結(jié)果 * * @param name 排序方法名 * @param operName 交換/復(fù)制 * @param start 開始時間 * @param end 結(jié)束時間 */ private static void printResult(String name,String operName,long start,long end){ System.out.print( name + "——比較次數(shù):" + 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(); // 輸出排序結(jié)果 printResult("冒泡排序","交換次數(shù)", 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; } } // 存在比當(dāng)前值還要小的值，則進(jìn)行位置對換，否則無需對調(diào)位置 if (minPosition != -1) { // 交換位置 swap(length, minPosition, array); } length++; } long end = new Date().getTime(); printResult("選擇排序","交換次數(shù)", 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; // 右移數(shù)字，實現(xiàn)cur下標(biāo)的左側(cè)都是有序的 while (cur > 0 && compare(temp, array[cur - 1]) < 0) { copy(cur-1,cur,array); cur--; } // 如果cur==i則說明數(shù)據(jù)項已經(jīng)在正確的位置了，不需要進(jìn)行交換 if (cur != i) { // 不滿足temp<array[cur-1]時，則當(dāng)前正在排的項temp已經(jīng)找到正確位置了 copyData(temp,cur,array); } } long end = new Date().getTime(); printResult("插入排序" ,"復(fù)制次數(shù)", 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); // 分割左側(cè) recMergeSort(array,workSpace, mid + 1, upperBound); // 分割右側(cè) 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("歸并排序","復(fù)制次數(shù)",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("希爾排序","復(fù)制次數(shù)",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; // 右移數(shù)字，實現(xiàn)cur下標(biāo)的左側(cè)都是有序的 while (cur > 0 && compare(temp, array[cur - 1]) < 0) { copy(cur-1,cur,array); cur--; } // 如果cur==i則說明數(shù)據(jù)項已經(jīng)在正確的位置了，不需要進(jìn)行交換 if (cur != i) { // 不滿足temp<array[cur-1]時，則當(dāng)前正在排的項temp已經(jīng)找到正確位置了 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){ // 查找左側(cè)子數(shù)組大于樞紐的位置 while(compare(array[++leftPtr],pivot)<0){ } // 查詢右側(cè)子數(shù)組小于樞紐的位置 while(compare(array[--rightPtr],pivot)>0){ } if(leftPtr>=rightPtr){ break; } // 交換需要調(diào)整位置的兩個數(shù)據(jù)項 swap(leftPtr,rightPtr,array); } // 將樞紐挪到兩側(cè)中間 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("快速排序","交換次數(shù)",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(); // 隨機數(shù)據(jù)項 進(jìn)行快速排序 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++; } // 對逆序的數(shù)組使用快速排序 System.out.print("對逆序序列排序："); quickSort(array6a); }}
