文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

分析排序算法的角度

算法的執行效率

算法的執行效率一般從時間復雜度以及比較、交換次數來考慮。

時間復雜度

時間復雜度需要考慮最好情況、最壞情況、平均情況時間復雜度。同時我們需要考慮復雜度的系數、常數和低階。這是因為時間復雜度反應的是數據規模n很大時候的一個增長趨勢，所以會忽略系數、常數、低階。但是實際軟件開發中，n可能是10、100、1000。這個時候就不能忽略系數、常數、低階。

比較、交換次數

我們常見的排序算法大多數是基于比較的。基于比較的排序算法會涉及比較和元素交換兩種操作。所以需要考慮。

內存消耗

有些排序算法的空間消耗是O(1)的，有些是O(n)。原地排序是空間復雜度是O(1)的排序算法。

算法的穩定性

排序算法的穩定性是指如果數組中有兩個值相同的元素，經過排序算法排序之后，這兩個元素的前后順序不發生變化。這種排序算法叫做穩定的排序算法。如果前后順序發生變化了，則稱為不穩定性排序算法。
用途是：一般排序的是一個對象。例如希望按照訂單金額從小到大排序訂單，金額相同的時候按照訂單時間從小到大排序。我們可以先按照訂單時間從小到大排序，然后按照訂單金額從小到大排序。如果是穩定的則可以實現這樣的要求。

總結：考核的指標有：最好時間復雜度、最壞時間復雜度、平均時間復雜度、比較次數、交換次數、空間復雜度、算法穩定性。

基于比較的排序算法比較

有序度

數組中具有有序關系的元素對的個數。有序元素對的表示是這樣的：

$a[i]<=a[j]，如果i<j$
一個數組中最大的有序度是$\frac{n?(n?1)}{2}$，稱為滿有序度。
逆序度=滿有序度-有序度

冒泡排序

特點：比較相鄰元素，交換的也是相鄰元素
空間復雜度：O(1)，原地排序
穩定性：穩定(只要相鄰元素相等不做交換)
最好時間復雜度：要排序的數組已經有序，需要冒泡一遍，O(n)。
最壞時間復雜度：順序剛好相反，需要n次冒泡，O($n^2$)。
平均時間復雜度：平均時間復雜度本來是一個加權平均值。但這里太過復雜，使用有序度來解決。
排序算法的時間復雜度主要由比較次數和交換次數決定。
因為每交換一次，數組的有序度加1。所以最少的交換次數是0，當輸入完全有序。最多$\frac{n?(n?1)}{2}$，當輸入完全無序。取個平均值表示初始有序度既不高也不低：$\frac{n?(n?1)}{4}$。也就是說平均情況下需要$\frac{n?(n?1)}{4}$次交換。
比較次數肯定多于交換次數，這個值的上限是O($n^2$)。
所以平均時間復雜度是O($n^2$)。

插入排序

特點：往一個有序的數組中插入一個元素。將數組分為有序區間和無序區間。
空間復雜度：O(1)，原地排序
穩定性：穩定
最好時間復雜度：如果輸入是已經排序好的，我們每次只在有序區間的末尾比較一次數據，所以是O(n)。注意：這里是從尾到頭遍歷已經排序好的數據。
最壞時間復雜度：如果是輸入是逆襲的，相當于每次在數組的第一個位置插入元素，需要移動大量的數據。復雜度O($n^2$)。
平均時間復雜度：在數組中插入一個數據的平均時間復雜度是O(n)（以前課程里面討論過）。循環插入n次。所以復雜度O($n^2$)。
一般項目中選擇插入排序。因為插入排序的數據交換工作比較簡單。隨機生成 10000 個數組，每個數組中包含 200 個數據。在我電腦上，冒泡排序394ms，插入排序6ms。

選擇排序

特點：將數組分為有序區間和無序區間。每次在無序區間選擇最小元素插入在有序區間末尾。
空間復雜度：O(1)，原地排序
穩定性：不穩定。找到的最小元素需要與前面的元素互換位置，可能改變相同元素的前后順序。
最好時間復雜度：因為選擇排序每次都需要在無序區間選擇最小元素，所以每次都需要n次比較。需要重復n次。所以復雜度O($n^2$)。
最壞時間復雜度：O($n^2$)
平均時間復雜度：O($n^2$)

歸并排序

特點：使用分治、分區的思想。例如解決下標從p到q數組的排序問題，可以先解決從p到r，從r+1到q兩個子數組的排序問題，然后將兩個子數組合并，就解決了。
空間復雜度：因為合并部分需要單獨申請空間，而最多申請O(n)。不是原地排序。
穩定性：只需要保證合并過程中相同元素前后位置不變，就可以保證穩定性。
時間復雜度：O(nlogn)。

快速排序

特點：使用分治、分區的思想。例如解決下標從p到q數組的排序問題。我們先選擇一個pivot元素，可以是a[q]。小于pivot的元素放在左邊，大于pivot的元素放在右邊，pivot放在中間，位置假如是i。然后再遞歸的解決從p到i-1的排序問題，從i+1到q的排序問題。
遞推公式：quick_sort(p…q) = quick_sort(p,i-1)+ quick_sort(i+1,q)
退出條件：p>=q
快速排序找到pivot元素的合適位置的函數是partition。這個函數的實現有一些技巧。
空間復雜度：O(1)，原地排序
最好時間復雜度：最好的情況是pivot每次可以將數組一分為二，時間復雜度O($nlogn$)。
最壞時間復雜度：如果每次pivot都將數組分成兩部分（自己和其他部分），時間復雜度就是O($n^2$)
平均時間復雜度：O($nlogn$)，以后的課程中會介紹。使用遞歸樹來理解。
分治、分區思想的拓展：用來解決無序問題。例如查找一個無序數組的第k大元素。我們選擇數組a[0…n-1]的最后一個元素a[n-1]作為pivot。對數組做原地拆分，變為a[0…p-1]、a[p]、a[p+1…n-1]。如果k=p+1，那么a[p]就是答案。如果k<p+1，那么答案在a[0…p-1]中，繼續做分區。如果k>p+1，則答案在a[p+1…n-1]，繼續做分區。

快速排序vs歸并排序

歸并排序是由下到上，先處理子問題（的排序問題），然后再合并。
快速排序是由上到下，先分區，再處理子問題（的排序問題）。

如何優化快速排序

快排在某些情況下時間復雜度會退化為$O(n^2)$。這種時候是因為選取的pivot每次都將數組分成了自己和其他兩個部分，如果選擇的pivot合適就不會出現這樣的情況。
1 三數取中法。可以選擇頭、尾、中間三個元素的中間值作為pivot。如果數組比較長，可以使用“五數取中法”、“十數取中法”。
2 隨機法。從要排序的區間中每次隨機選擇一個數作為pivot。從概率角度講，有選擇不合適的時候，但不會每次都不合適。

快排可以優化的還有空間。快排使用的是遞歸，會因為棧大小的限制，引起棧溢出。可以在堆上模擬實現一個函數調用棧，手動模擬遞歸出棧、壓棧的過程，這樣就沒有棧空間大小限制了。

線性排序算法

桶排序

特點：將要排序的數據放入幾個桶，每個桶內的數據再單獨排序。按照桶依次取出就實現了整體數據排序。
應用范圍：1 要排序的數據能夠很容易劃分到m個桶。并且桶之間有天然的大小關系。2 各個桶的數據分布要均勻，如果集中在一個桶，那就沒有意義了。3 比較適合外部排序，數據量太大，不能在內存中完成排序。
時間復雜度：在桶的個數m非常接近數組大小n的時候，接近O(n)，實際是O(nlog(n/m))。
空間復雜度：O(n)
穩定性: 取決于每個桶的排序方式，快排就不穩定，歸并就穩定。

計數排序

特點：是桶排序的特殊化。每個桶內放的值是相同的。例如考生排名。
時間復雜度：O(n)。
計數排序的計數方法是需要了解的。（圖片來自極客時間）

例如有8個考生，成績分別是A[8]={2,5,3,0,2,3,0,3}。計算得到每個考生的排名。
1 用C[6]表示桶數組，遍歷一遍得到C[6]={2,0,2,3,0,1}。
2 我們對C數組順序求和得到C[6]={2,2,4,7,7,8}。C[k]存儲小雨等于分數k的考生個數。
3 從后向前一次掃描數組A，k=A[i]，idx=C[k]-1,R[idx]=k,C[k]=C[k]-1。這樣就知道考試得分是k的考生，排名是idx。
代碼

考生排名一般用JDK自帶的排序算法即可實現。這樣的時間復雜度一般為O(nlogn)。當成績是一個整數的時候可以使用計數排序在O(n)時間內完成。代碼

應用范圍：計數排序只能用在數據范圍不大的場景中。如果數據范圍k比數組長度n大很多，就不適合了。計數排序只能給出非負整數的排序。如果要排序的數據是基于其他類型的，需要調整到非負整數的范圍。
穩定性: 穩定，只要整理最后結果時從后開始遍歷即可。

基數排序

特點：如果有10萬個手機號碼，從小到大排序。因為數據范圍大，桶排序和計數排序都不適合。可以先按照最后一位排序，接著按照倒數第二位排序…一直到按照第一位排序。使用穩定排序算法。經過11次排序之后，手機號碼就有序了。
應用范圍：可以分割出單獨的每一位，而且位之間有遞進關系（a的高位大于b的高位=>a大于b）。每一位的數據范圍不能太大，要可以使用線性排序。
時間復雜度：O(k*n)。每一位按照桶排序或者計數排序實現，需要排序k次。
穩定性：穩定，而且必須穩定。

業務思考題

1 為什么插入排序比冒泡排序更受歡迎？
2 用快排思想在O(n)內找第k大元素？
3 現在你有10個接口訪問日志文件，每個文件大小約300MB，每個文件里的日志都是按照時間戳從小到大排序的。你希望將這10個較小的日志文件合并為1個日志文件，合并之后的日志仍然按照時間戳從小到大排序。如果處理上述排序任務的機器內存只有1GB，怎么做？
4 如何根據年齡給100萬用戶數據排序？
5 假設我們現在需要對D,a,F,B,c,A,z這個字符串進行排序，要求將其中所有小寫字母都排在大寫字母前面，但小寫字母內部和大寫字母內部不要求排序。

總結

以上是生活随笔為你收集整理的算法一——排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。