最詳細的排序解析，理解七大排序

mp.weixin.qq.com

點擊上方“方志朋”，選擇“置頂或者星標”

你的關注意義重大！

注：

lgN在這里為1og₂N簡寫
為了方便描述,本文默認用int類型比較，從小到大排序
本文排序算法以java語言實現
本文的排序都是比較排序
比較次數和賦值和交換次數有的排序不好分析，可能不準確

一.插入排序

對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入

從第一個元素開始，該元素認為已經被排序；
取出下一個元素，在已排序的元素序列中從后向前掃描；
如果已排序元素大于新元素，新元素繼續比較前一個元素，直到找到已排序的元素小于或者等于新元素的位置；
將新元素插入到該位置后；
重復步驟2~4。

java實現

public static void insertionSort(int[] a){int insertIndex,insertElement;for(int i = 1; i < a.length; i++){ //外層循環，默認第一個元素有序，從第二個元素開始，時間復雜度NinsertIndex = i - 1; //插入的位置，默認有序數列的最后一個元素的位置insertElement = a[i]; //新插入的元素，默認外層循環的元素while(insertIndex >= 0 && a[insertIndex] > insertElement){ //內層循環，只要新元素比待插入位置的元素小就繼續，時間復雜度Na[insertIndex + 1] = a[insertIndex]; //比待插入元素大的元素后移一位insertIndex--; //插入位置前移一位}a[insertIndex + 1] = insertElement; //內層循環結束，把新元素放到插入位置后面}
}

插入排序為兩層循環嵌套，時間復雜度O(N²),插入排序的while循環是先比較，移動待插入的位置，循環結束才真正交換數據位置。這里需要注意，常用的for循環嵌套進行插入排序會導致每次插入一直和前面元素交換直到插入到待插入位置，上面的內循環用while尋找待插入位置，把其他元素后移的算法更合理，每次插入只一次進行一次交換。因插入排序每次只比較一位，對于逆序較多的數組效率較低，衍生算法希爾排序，會大幅加快逆序交換，后面詳細介紹。

二.選擇排序

在未排序序列中找到最小元素，放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小元素，然后放到已排序序列的末尾，循環直到所有元素均排序完畢。

初始狀態：無序區為R[1..n]，有序區為空；
第i趟排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為R[1..i-1]和R[i..n]。該趟排序從當前無序區中選出最小的記錄 R[k]，將它與無序區的第1個記錄R[i]交換，使R[1..i]和R[i+1..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；
循環n-1次，排序完成。

java實現

public static void selectionSort(int[] a){int minIndex,temp;for(int i = 0; i < a.length - 1; i++){ //外層循環，從無序區第一個元素開始到數組倒數第二個元素，時間復雜度NminIndex = i; //每次外層循環假設無序區第一個元素是最小元素for(int j = i + 1; j < a.length; j++){	//內層循環，從假設的最小元素的后一個位置開始，到數組最后一個元素，時間復雜度Nif(a[j] < minIndex){ //判斷內層循環的元素是否小于假設的最小元素	minIndex = j; //如果比最小元素小，標記該元素的位置為新的最小元素的位置，內層循環完畢，會找出無序區的最小值	}} temp = a[i]; 		a[i] = a[minIndex];a[minIndex] = temp;	//無序區真正最小值和第一個元素交換位置，下一次循環無序區從下一個值開始}
}

選擇排序為兩層for循環嵌套，內層循環始終去找最小值，放到最前面。交換次數比冒泡排序少很多，所以實際執行效率比冒泡排序快。衍生算法，雙向選擇排序（每次循環，同時選出最大值放在末尾，最小值放在前方），可以提高選擇效率。

三.冒泡排序

重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換

初始狀態：無序區為R[1..n]，有序區為空；
第i趟排序(i=0,1,2…n-1)開始時，當前無序區和有序區分別為R[0..n-i]和R[n-i+1..n]。對每一對相鄰元素進行比較，從開始第一對到結尾的最后一對，如果第一個比第二個大，就交換它們兩個，這樣在最后的元素應該會是最大的數，使R[1..n-i-1]和R[n-i..n]分別變為記錄個數減少1個的新無序區和記錄個數增加1個的新有序區；
循環n-1次，直到排序完成。

java實現

public static void bubbleSort(int[] a){int temp;for(int i = 0; i < a.length - 1; i++){ //外層循環，從數組第一個元素到倒數第二個元素，時間復雜度為Nfor(int j = 0; j < a.length - 1 -i; j++){ //內層循環，從數組第一個元素到剩余的元素（減去有序區的元素）if(a[j] > a[j+1]){ temp = a[j+1];a[j+1] = a[j];a[j] = temp; //相鄰元素只要前面的比后面的大，就交換位置}}}
}

冒泡排序在代碼實現上是最簡單的，不需要什么思考，兩層for循環嵌套，比大小交換。因為冒泡通常的例子都是讓大的往后移，對于剛接觸排序的人來說看來上面可能認為冒泡排序與選擇排序是反向操作，其實冒泡排序也可以把小數向前移，這樣能明顯的看出冒泡排序和選擇的排序的不同，針對無序區的元素，冒泡排序總是不斷地交換，而選擇排序是先找出最小的元素再做一次交換。衍生算法，雞尾酒排序，該排序從左往右找出最大值后，再從右往左，找出最小值，類似雞尾酒攪拌左右循環。在某些情況下，優于冒泡排序，以序列(2,3,4,5,1)為例，雞尾酒排序只需要訪問兩次（升序降序各一次）次序列就可以完成排序，但如果使用冒泡排序則需要四次。

四.希爾排序

插入排序的改進版，優先比較距離遠的元素，減少交換次數

1.選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1； 2.按增量序列個數k，對序列進行k 趟排序； 3.每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

java實現

public static void shellSort(int[] a){int h = 1； //希爾排序是使間隔為h的元素有序int temp;while(h < a.length/3) { //while循環，擴大hh = 3*h + 1; //這里用3倍作為希爾排序的間隔，是常用的值，加1是為了防止排序的都是3的倍數}while(h >= 1){ //while循環讓h從大到小插入排序for(int i = h; i < a.length; i++){ ?//從h位置開始，對整個數組遍歷，i為插入元素的位置temp = a[i]; 把i當前值保存到temp中for(int j = i - h; j > 0 && a[j] > temp ;j -= h){ //遍歷把i每隔h位進行比較，確定插入的位置a[j + h] = a[j]; ?//如果前面的元素大于temp，把前面元素的值放在后面}a[j + h] = temp; //把原來i的值賦值給前面元素，此時發生了j -=h，實際上j + h等于循環里的j}h = h/3; //更大間隔的插入完成，縮小插入間隔}
}

上面是常用的寫法，每次比較，如果前面的更大都會交換，可以優化一下,直接把上面插入算法嵌入內循環，比較的間隔由1改為h,比較的時候只移動插入位置，比較完只需交換一次 java實現

public static void shellSort(int[] a){int h = 1； //希爾排序是使間隔為h的元素有序int insertIndex,insertElement;while(h < a.length/3) { //while循環，擴大hh = 3*h + 1; //這里用3倍作為希爾排序的間隔，是常用的值，加1是為了防止排序的都是3的倍數}while(h >= 1){ //while循環讓h從大到小插入排序for(int i = h; i < a.length; i++){ ?//從h位置開始，對整個數組遍歷，i為插入元素的位置insertIndex = i - h; //插入的位置，默認前面間隔h的位置insertElement = a[i]; //新插入的元素，默認外層循環的最后一個元素while(insertIndex >= 0 && a[insertIndex] > insertElement){ //內層循環，只要新元素比待插入位置的元素小就繼續a[insertIndex + h] = a[insertIndex]; //比待插入元素大的元素后移h位insertIndex -= h; //插入位置前移h位}a[insertIndex + h] = insertElement; //內層循環結束，把新元素放到插入位置后面}h = h/3; //更大間隔的插入完成，縮小插入間隔}
}

希爾排序的時間復雜度與增量序列的選取有關，例如希爾增量時間復雜度為O(N2)，而Hibbard增量的希爾排序的時間復雜度為O(N^1.5)，希爾排序時間復雜度的下界是Nlg2N。希爾排序沒有快速排序算法快 O(N(lgN))，因此中等大小規模表現良好，對規模非常大的數據排序不是最優選擇。但是比O(N2)復雜度的算法快得多。并且希爾排序非常容易實現，算法代碼短而簡單。此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞的情況下執行的效率會非常差。

五.堆排序

堆就是完全二叉樹，分為最大堆和最小堆，最大堆要求節點的元素都要不小于其孩子（最小堆要求節點元素都不大于其左右孩子），對左右孩子的大小關系不做要求，所以處于最大堆的根節點的元素一定是這個堆中的最大值。堆排序算法就是抓住了堆的這一特點，每次都取堆頂的元素，將其放在序列最后面，然后將剩余的元素重新調整為最大堆，依次類推，最終得到排序的序列。

1.將初始待排序關鍵字序列(R1,R2….Rn)構造成最大堆，此堆為初始的無序區； 2.將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]； 3.由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。

java實現

public static void heapSort(int[] a){int N = a.length;for(int k = N/2; k >= 1; k--){ //for循環用來構造堆，最終生成最大堆sink(a,k,N);}while(N > 1){ //循環排序無序區exch(a,1,N--); //堆頂a[1]與堆的最后一個元素a[N]交換位置，并且去掉最后一個元素到有序區，減小新堆sink(a,1,N); //重新生成為最大堆}
}/*** 從上至下堆有序化*/
private static void sink(int[] a,int k,int N){ while(2*k <= N) {int j = 2*k;if(j < N && a[j] < a[j+1]){ //j<n保證j+1不越界，a[j]和a[j+1]是a[k]的左右子節點，這里是為了選取兩個子節點較大的一個，a[j]大取a[j],a[j]小取a[j++]>= a[j]) { //如果父節點大于等于值大的子節點，堆有序，終止循環break；	}if(a[k] >= a[j]) { //如果父節點大于等于值大的子節點，堆有序，終止循環break；	}exch(a,k,j); //交換值大的子節點和父節點的值，達到堆有序k = j; //子節點，作為下一個循環的父節點，繼續下沉}
}/*** 交換兩個元素*/
private static void exch(int[] a,int i,int j){int temp = a[i];a[i] = a[j];a[j] = temp;
}}</n保證j+1不越界，a[j]和a[j+1]是a[k]的左右子節點，這里是為了選取兩個子節點較大的一個，a[j]大取a[j],a[j]小取a[j++]>

因為堆的父節點k的子節點為2k和2k+1，下標為0會導致父節點和左子節點都是0，所以上述排序的數組從下標從1開始比較方便。堆排序只需要NlgN的時間，而且算法穩定，只需要少量輔助空間，是最優的利用時間和空間的方法，但因為它的緩存命中率低，應用很少用它，多用于嵌入式。

六.歸并排序

遞歸的把已有序列均分為兩個子序列，使子序列有序，合并子序列 1.把長度為n的輸入序列分成兩個長度為n/2的子序列； 2.對這兩個子序列分別采用歸并排序； 3.將兩個排序好的子序列合并成一個最終的排序序列。

java實現

private static int[] aux; //歸并所需的輔助數組
public static void mergeSort(int[] a){aux = new int[a.length];sort(a,0,a.length-1); //開始遞歸排序
}/*** 遞歸的排序歸并*/	
private static void sort(int[] a,int left,int right){if(right <= left){ //排序從左到右，確保右邊比左邊大return;}int mid = (left + right)/2; //找出中間位置sort(a,left,mid); //將左半邊排序sort(a,mid+1,right); //將右半邊排序merge(a,left,mid,right); //歸并結果
}/*** 原地歸并方法*/
private static void merge(int[] a,int left,int mid,int right){ //將a[left..mid]和a[mid+1..right]歸并int i = left,j = mid + 1; ?//左右半邊起始位置for(int k = left; k <= right; k++){ //將a[left..right]復制到aux[left..right]aux(k) = a(k);}for(int k = left; k <= right; k++){ //歸并回到a[left..right]if(i > mid){ ?//i比mid大代表左半邊用完，只有右半邊有元素a[k] = aux[j++]; //右邊元素給a[k]}else if(j > right){ //j比right大代表右半邊用完，只有左半邊有元素a[k] = aux[i++]; //左邊元素給a[k]}else if(aux[j] < aux[i]){ //如果右邊元素大于左邊a[k] = aux[j++]; //右邊元素給a[k]	}else{	//否則左邊大于等于右邊a[k] = aux[i++]; //左邊元素給a[k]}}
}

歸并排序是分治法的典型應用，高效穩定，但是歸并排序需要一個數組長度的輔助空間，在空間成本高的時候不適合使用

七.快速排序

通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

1.從數列中挑出一個元素，稱為 “基準”（pivot）； 2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作； 3.遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

java實現

public static void quickSort(int[] a){sort(a,0,a.length-1);
}/*** 遞歸進行快速排序*/
private static void sort(int[] a,int left,int right){if(right <= left){ //排序從左到右，確保右邊比左邊大return;}int j = partition(a,left,right); //切分sort(a,left,j-1); //將左半邊排序sort(a,j+1,right); //將右半邊排序
}/*** 快速排序切分*/
private static int partition(int[] a,int left,int right){ int i = left,j = right + 1; //左右掃描指針int v = a[left]; //選取切分元素，這里選第一個，實際數據可以自行挑選while(true){while(a[++i] < v){ //a[i]<v時增大i，只要比v小繼續往右掃描 i="=" v="">< a[--j]){ //a[j]>v時減小j，只要比v大繼續往左掃描if(j == left){ //掃描到左邊則終止break;}}while(v < a[--j]){ //a[j]>v時減小j，只要比v大繼續往左掃描if(j == left){ //掃描到左邊則終止break;}}if(i >= j){ //如果左右指針交叉，終止循環break; }exch(a,i,j); //不滿足上述條件（左邊比v大，右邊比v小，指針未交叉），左右元素交換位置}exch(a,left,j); //將切分元素v放入正確的位置return j; //a[left..j-1]<=a[j]<=a[j+1..right]，并返回j
}/*** 交換兩個元素*/
private static void exch(int[] a,int i,int j){int temp = a[i];a[i] = a[j];a[j] = temp;
}</v時增大i，只要比v小繼續往右掃描>

快速排序是通常情況下的最優選擇，高效，只需要lgN級別的輔助空間，但是快速排序不穩定，受切分點的影響很大

七種排序總結

上面詳細介紹了七種排序的實現細節和特點，下面的表格總結了七種排序的各種特征。

其中插入排序，選擇排序，冒泡排序都是簡單排序，時間復雜度是O(N²),其中插入排序和冒泡排序適合原始序列有序的數組，選擇排序的交換和賦值次數會比較少，可以根據不同環境和數據的實際情況和長度選擇具體的排序。整體插入排序優于選擇排序優于冒泡排序。希爾排序是插入排序的優化，突破了前三個排序O(N²)的時間復雜度，但是本質還是插入排序，突破比較相鄰元素的慣性思維，直接比較一定間隔的元素，大幅度減少了逆序調整的比較次數和交換次數，從而達到比較理想的算法復雜度，適合對中等規模數組進行排序。堆排序是利用了最大堆的特點，始終把堆頂元素（最大元素）和最后一個元素替換，再重新構造最大堆，重復執行達到排序的效果。堆結構的特性讓算法的復雜度降低到NlgN級別，但是有不方便索引元素的確定，緩存命中率較低。而歸并排序則是充分運用了分治原理，把大問題不斷的拆分成小問題，進行排序，再合并小數組達到整體排序的目標，歸并排序即高效又可靠，唯一的缺點是需要數組長度的輔助空間，在空間成本低的時候適合使用。快速排序則解決了歸并排序占用空間的問題，在數組內部用很小的輔助棧，即可完成對元素的分離，再去解決分離后的更小的數組，正常情況下擁有和歸并相同級別的時間復雜度，但是得注意選取好切分元素。實際上一個復雜的序列可能用不止一種排序，例如分治和快速排序在分割到很小的序列時再進行分割反而效率不如插入排序等簡單排序，可以設置一定的閾值，先用分治或者快速排序的方式分割數組，再轉換成插入等簡單排序完成最終的排序。

希望本文大家加深對排序的理解有所幫助。我的微信公眾號：程序之路，會持續發布技術成長文章，歡迎長按下圖關注