前言

今天繼續(xù)算法學(xué)習(xí)，本次學(xué)習(xí)的是高級排序之快速排序。本文代碼部分存在調(diào)用公共方法，可在文章：簡單排序算法之冒泡、插入和選擇排序-Java實(shí)現(xiàn)版 ，高級排序之歸并排序、希爾排序。中查找相關(guān)方法，另外，本文也提供測試時(shí)使用的完整代碼，對其他算法不感興趣，可在文末找到完整源代碼。

快速排序

快速排序的本質(zhì)就是把一個(gè)數(shù)組劃分為兩個(gè)子數(shù)組，然后遞歸地調(diào)用自身為每一個(gè)數(shù)組進(jìn)行“快速排序”來實(shí)現(xiàn)的。這里就涉及一個(gè)問題：如何劃分？

在快速排序中，為了劃分?jǐn)?shù)組，提出了“樞紐”這個(gè)詞，它代表待排序序列中的一個(gè)數(shù)據(jù)項(xiàng)?？焖倥判蚶脴屑~將數(shù)組劃分成兩部分，一部分（樞紐左側(cè)）是所有小于該樞紐表示的數(shù)據(jù)項(xiàng)，另一部分（樞紐右側(cè)）則都大于該樞紐表示的數(shù)據(jù)項(xiàng)（注意，此時(shí)左右兩側(cè)的數(shù)據(jù)項(xiàng)是無序的），樞紐放置在左右兩側(cè)的中間，此時(shí)該樞紐已經(jīng)處在排序的正確位置上了（樞紐是快速排序所排序的對象，實(shí)現(xiàn)“排序”的關(guān)鍵點(diǎn)就是調(diào)整樞紐的位置）。通過遞歸的這樣劃分，最終出現(xiàn)左側(cè)只有一個(gè)數(shù)據(jù)項(xiàng)（該數(shù)據(jù)項(xiàng)既是左側(cè)子數(shù)組又是樞紐），則結(jié)束左側(cè)遞歸，開始劃分右側(cè)數(shù)組。。。以此類推。這里又產(chǎn)生了一個(gè)問題，如何選擇樞紐？

選擇樞紐的算法：最簡單的選擇樞紐算法就是每次遞歸都選擇數(shù)組的最后一個(gè)數(shù)據(jù)項(xiàng)做為樞紐（或者選擇最左側(cè)的數(shù)據(jù)項(xiàng)作樞紐）。

上圖演示了以子數(shù)組最右側(cè)數(shù)據(jù)項(xiàng)做樞紐的排序過程

代碼演示（樞紐始終使用子數(shù)組的最右側(cè)數(shù)據(jù)項(xiàng)）

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&&compare(array[–rightPtr],pivot)>0){ } if(leftPtr>=rightPtr){ break; } // 交換需要調(diào)整位置的兩個(gè)數(shù)據(jù)項(xiàng) 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); }

運(yùn)行結(jié)果

冒泡排序——比較次數(shù):49995000,交換次數(shù):25153125,耗時(shí):173毫秒

選擇排序——比較次數(shù):49995000,交換次數(shù):9987,耗時(shí):65毫秒

插入排序——比較次數(shù):25075792,復(fù)制次數(shù):25075793,耗時(shí):42毫秒

歸并排序——比較次數(shù):120459,復(fù)制次數(shù):267232,耗時(shí):3毫秒

希爾排序——比較次數(shù):233896,復(fù)制次數(shù):238266,耗時(shí):5毫秒

對隨機(jī)序列排序：快速排序——比較次數(shù):165181,交換次數(shù):31700,耗時(shí):3毫秒

對逆序序列排序：快速排序——比較次數(shù):49825881,交換次數(shù):9976,耗時(shí):54毫秒

從運(yùn)行結(jié)果中，可以看到對于隨機(jī)序列，快速排序算法執(zhí)行速度是非常快的，和歸并排序相同，但給逆序序列排序時(shí)，效果則非常差，幾乎和選擇排序一樣的效率了。那這是為什么呢？

根本原因，就在于樞紐的選擇上，快速排序期望樞紐能夠?qū)?shù)組拆分成兩個(gè)長度幾乎相同的子數(shù)組，這樣能最優(yōu)的平衡比較次數(shù)和交換次數(shù)。對于隨機(jī)序列，簡單的選擇最右側(cè)數(shù)據(jù)項(xiàng)做為樞紐不至于頻繁出現(xiàn)左右子數(shù)組極度不平衡的情況，而對于逆序序列，則幾乎每次劃分都是極度不平衡的兩個(gè)子數(shù)組，最終導(dǎo)致較大側(cè)的子數(shù)組要被劃分更多次。

優(yōu)化樞紐選擇算法

快速排序的最優(yōu)劃分結(jié)果是劃分的兩個(gè)數(shù)組長度相等，為了達(dá)到這個(gè)目的，我們每次都要在劃分前，先找到子數(shù)組的中間數(shù)據(jù)項(xiàng)嗎？顯然，不能這么做的，因?yàn)楹芸赡苣阏抑兄档臅r(shí)間遠(yuǎn)遠(yuǎn)大于你排序的時(shí)間了。所以，我們只能選擇一個(gè)實(shí)現(xiàn)既不是過于復(fù)雜，又比“選擇最右側(cè)數(shù)據(jù)項(xiàng)做為樞紐”的算法更具普適性。

上圖所示取樞紐的方法叫“三數(shù)據(jù)項(xiàng)取中”，即從數(shù)組中選擇第一個(gè)、最后一個(gè)以及中間的數(shù)據(jù)項(xiàng)，從這三個(gè)數(shù)據(jù)項(xiàng)中取出大小在中間的項(xiàng)做為樞紐，在選擇過程中，我們實(shí)際上也對這三個(gè)數(shù)據(jù)項(xiàng)做了排序，那順便把分別大于、小于樞紐的那兩個(gè)數(shù)據(jù)項(xiàng)也放到正確的位置（即左側(cè)小于樞紐，右側(cè)大于樞紐）。

該方法每次劃分都需要至少有三個(gè)數(shù)據(jù)項(xiàng)，所以當(dāng)子數(shù)組項(xiàng)數(shù)不大于3個(gè)的時(shí)候，就可以結(jié)束遞歸劃分了，此時(shí)的排序可以通過其他排序算法實(shí)現(xiàn)，如使用手動排序（待排序的數(shù)據(jù)項(xiàng)不大于3個(gè)，所以手動排序完全可以輕松搞定），也可以使用插入排序（如果使用插入排序，我們甚至可以當(dāng)數(shù)據(jù)項(xiàng)不大于10（這個(gè)10沒有具體意義，你也可以20、30）的時(shí)候就可以用插入排序來收尾了）。下面我們用該方法來選擇樞紐（用插入排序來收尾），對代碼進(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 0 && compare(temp, array[cur – 1]) =rightPtr){ break; } // 交換需要調(diào)整位置的兩個(gè)數(shù)據(jù)項(xiàng) 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); }

運(yùn)行結(jié)果

冒泡排序——比較次數(shù):49995000,交換次數(shù):25138570,耗時(shí):170毫秒

選擇排序——比較次數(shù):49995000,交換次數(shù):9990,耗時(shí):65毫秒

插入排序——比較次數(shù):25069178,復(fù)制次數(shù):25069176,耗時(shí):34毫秒

歸并排序——比較次數(shù):120483,復(fù)制次數(shù):267232,耗時(shí):2毫秒

希爾排序——比較次數(shù):231598,復(fù)制次數(shù):235991,耗時(shí):6毫秒

對隨機(jī)序列排序：快速排序——比較次數(shù):154857,交換次數(shù):44570,耗時(shí):3毫秒

對逆序序列排序：快速排序——比較次數(shù):188034,交換次數(shù):20067,耗時(shí):1毫秒

從執(zhí)行結(jié)果可以看出，優(yōu)化過樞紐選擇算法后，無論是隨機(jī)序列排序還是逆序序列排序，排序速度都非常快。

至此，本文結(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; /** * 生成隨機(jī)數(shù)數(shù)組 * * @return */ public static int[] buildRandomArray() { int[] array = new int[ARRAY_SIZE]; for (int i = 0; i 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 開始時(shí)間 * @param end 結(jié)束時(shí)間 */ private static void printResult(String name,String operName,long start,long end){ System.out.print( name + “——比較次數(shù):” + compareCount + “,”+operName+”:” + swapCount + “,耗時(shí):” + (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 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){ 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 0 && compare(temp, array[cur – 1]) =rightPtr){ break; } // 交換需要調(diào)整位置的兩個(gè)數(shù)據(jù)項(xiàng) 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 =0;i–){ array6a[j] = array6[i]; j++; } // 對逆序的數(shù)組使用快速排序 System.out.print(“對逆序序列排序：”); quickSort(array6a); }}

原文格式更佳：高級排序算法之快速排序|NGUP的個(gè)人技術(shù)博客