合並排序的遞歸演算法
❶ 幾種排序方法
這兩天復習了一下排序方面的知識，現將目前比較常見的整理一下。 選擇排序選擇排序的思想是首先先找到序列中最大元素並將它與序列中最後一個元素交換，然後找下一個最大元素並與倒數第二個元素交換，依次類推。此排序很簡單，這不做多說，代碼實現如下：View Code插入排序演算法流程：1. 從第一個元素開始，該元素可以認為已經被排序 2. 取出下一個元素，在已經排序的元素序列中從後向前掃描 3. 如果該元素（已排序）大於新元素，將該元素移到下一位置 4. 重復步驟3，直到找到已排序的元素小於或者等於新元素的位置 5. 將新元素插入到下一位置中 6. 重復步驟2View Code冒泡排序依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。至此第一趟結束，將最大的數放到了最後。在第二趟：仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再小於第2個數），將小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。 View Code合並排序在介紹合並排序之前，首先介紹下遞歸設計的技術，稱為分治法。分治法的核心思想是：當問題比較小時，直接解決。當問題比較大時，將問題分為兩個較小的子問題，每個子問題約為原來的一半。使用遞歸調用解決每個子問題。遞歸調用結束後，常常需要額外的處理，將較小的問題的結果合並，得到較大的問題的答案。 合並排序演算法在接近數組中間的位置劃分數組，然後使用遞歸運算對兩個一半元素構成的數組進行排序，最後將兩個子數組進行合並，形成一個新的已排好序的數組。 代碼如下：View Code快速排序快速排序與合並排序有著很多相似性。將要排序的數組分成兩個子數組，通過兩次遞歸調用分別對兩個數組進行排序，再將已經排好序的兩個數組合並成一個獨立的有序數組。但是，將數組一分為二的做法比合並排序中使用的簡單方法復雜的多。它需要將所有小於或者等於基準元素的元素放置到基準元素前面的位置，將大於基準的元素放置到基準後面的位置。 View Code堆排序View Code大概常用的幾種排序就這幾種，希望大家多多指正。
❷ 誰能給個以C++語言為基礎的歸並排序法啊，最好有例子哈````
可以運用分而治之方法來解決排序問題，該問題是將n 個元素排成非遞減順序。分而治之方法通常用以下的步驟來進行排序演算法：若n 為1，演算法終止；否則，將這一元素集合分割成兩個或更多個子集合，對每一個子集合分別排序，然後將排好序的子集合歸並為一個集合。
假設僅將n 個元素的集合分成兩個子集合。現在需要確定如何進行子集合的劃分。一種可能性就是把前面n- 1個元素放到第一個子集中（稱為A），最後一個元素放到第二個子集里（稱為B）。按照這種方式對A遞歸地進行排序。由於B僅含一個元素，所以它已經排序完畢，在A排完序後，只需要用程序2 - 1 0中的函數i n s e r t將A和B合並起來。把這種排序演算法與I n s e r t i o n S o r t（見程序2 - 1 5）進行比較，可以發現這種排序演算法實際上就是插入排序的遞歸演算法。該演算法的復雜性為O (n 2 )。把n 個元素劃分成兩個子集合的另一種方法是將含有最大值的元素放入B，剩下的放入A中。然後A被遞歸排序。為了合並排序後的A和B，只需要將B添加到A中即可。假如用函數M a x（見程序1 - 3 1）來找出最大元素，這種排序演算法實際上就是S e l e c t i o n S o r t（見程序2 - 7）的遞歸演算法。
假如用冒泡過程（見程序2 - 8）來尋找最大元素並把它移到最右邊的位置，這種排序演算法就是B u b b l e S o r t（見程序2 - 9）的遞歸演算法。這兩種遞歸排序演算法的復雜性均為(n2 )。若一旦發現A已經被排好序就終止對A進行遞歸分割，則演算法的復雜性為O(n2 )（見例2 - 1 6和2 - 1 7）。
上述分割方案將n 個元素分成兩個極不平衡的集合A和B。A有n- 1個元素，而B僅含一個元素。下面來看一看採用平衡分割法會發生什麼情況： A集合中含有n/k 個元素，B中包含其餘的元素。遞歸地使用分而治之方法對A和B進行排序。然後採用一個被稱之為歸並（ m e rg e）槐塌的過程，將已排好序的A和B合並成一個集合。
例2-5 考慮8個元素，值分別為[ 1 0，4，6，3，8，2，5，7 ]。如果選定k = 2，則[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]將被分別獨立地排序。結果分鉛廳圓別為[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。從兩個序列的頭部開始歸並這兩個已排序的序列。元素2比3更小，被移到結果序列；3與5進行比較，3被移入結果序列；4與5比較，4被放入結果序列；5和6比較，.。如果選擇k= 4，則序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]將被排序。排序結果分別為[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6 , 7 , 8 ]。當這兩個排好序的序列被歸並後，即可得所需要的排序序列。
圖2 - 6給出了分而治之排序演算法的偽代碼。演算法中子集合的數目為2，A中含有n/k個元素。
template
void sort( T E, int n)
{ / /對E中的n 個元素進行排序， k為全局變數
if (n >= k) {
i = n/k;
j = n-i;
令A 包含E中的前i 個元素
令B 包含E中餘下的j 個元素
s o r t ( A , i ) ;
s o r t ( B , j ) ;
m e rge(A,B,E,i,j,); //把A 和B 合並到E
}
else 使用插入排序演算法對E 進行排序
}
圖14-6 分而治之排序演算法的偽代碼
從對歸並過程的簡略描述中，可以明顯地看出歸並n個元素所伏頌需要的時間為O (n)。設t (n)為分而治之排序演算法（如圖1 4 - 6所示）在最壞情況下所需花費的時間，則有以下遞推公式：
其中c 和d 為常數。當n / k≈n-n / k 時，t (n) 的值最小。因此當k= 2時，也就是說，當兩個子集合所包含的元素個數近似相等時， t (n) 最小，即當所劃分的子集合大小接近時，分而治之演算法通常具有最佳性能。
可以用迭代方法來計算這一遞推方式，結果為t(n)= (nl o gn)。雖然這個結果是在n為2的冪時得到的，但對於所有的n，這一結果也是有效的，因為t(n) 是n 的非遞減函數。t(n) =(nl o gn) 給出了歸並排序的最好和最壞情況下的復雜性。由於最好和最壞情況下的復雜性是一樣的，因此歸並排序的平均復雜性為t (n)= (nl o gn)。
圖2 - 6中k= 2的排序方法被稱為歸並排序（ m e rge sort ），或更精確地說是二路歸並排序（two-way merge sort）。下面根據圖1 4 - 6中k= 2的情況（歸並排序）來編寫對n 個元素進行排序的C + +函數。一種最簡單的方法就是將元素存儲在鏈表中（即作為類c h a i n的成員（程序3 -8））。在這種情況下，通過移到第n/ 2個節點並打斷此鏈，可將E分成兩個大致相等的鏈表。
歸並過程應能將兩個已排序的鏈表歸並在一起。如果希望把所得到C + +程序與堆排序和插入排序進行性能比較，那麼就不能使用鏈表來實現歸並排序，因為後兩種排序方法中都沒有使用鏈表。為了能與前面討論過的排序函數作比較，歸並排序函數必須用一個數組a來存儲元素集合E，並在a 中返回排序後的元素序列。為此按照下述過程來對圖1 4 - 6的偽代碼進行細化：當集合E被化分成兩個子集合時，可以不必把兩個子集合的元素分別復制到A和B中，只需簡單地在集合E中保持兩個子集合的左右邊界即可。接下來對a 中的初始序列進行排序，並將所得到的排序序列歸並到一個新數組b中，最後將它們復制到a 中。圖1 4 - 6的改進版見圖1 4 - 7。
template
M e rgeSort( T a[], int left, int right)
{ / /對a [ l e f t : r i g h t ]中的元素進行排序
if (left < right) {//至少兩個元素
int i = (left + right)/2; //中心位置
M e rgeSort(a, left, i);
M e rgeSort(a, i+1, right);
M e rge(a, b, left, i, right); //從a 合並到b
Copy(b, a, left, right); //結果放回a
}
}
圖14-7 分而治之排序演算法的改進
可以從很多方面來改進圖1 4 - 7的性能，例如，可以容易地消除遞歸。如果仔細地檢查圖1 4 - 7中的程序，就會發現其中的遞歸只是簡單地重復分割元素序列，直到序列的長度變成1為止。當序列的長度變為1時即可進行歸並操作，這個過程可以用n 為2的冪來很好地描述。長度為1的序列被歸並為長度為2的有序序列；長度為2的序列接著被歸並為長度為4的有序序列；這個過程不斷地重復直到歸並為長度為n 的序列。圖1 4 - 8給出n= 8時的歸並（和復制）過程，方括弧表示一個已排序序列的首和尾。
初始序列[8] [4] [5] [6] [2] [1] [7] [3]
歸並到b [4 8] [5 6] [1 2] [3 7]
復制到a [4 8] [5 6] [1 2] [3 7]
歸並到b [4 5 6 8] [1 2 3 7]
復制到a [4 5 6 8] [1 2 3 7]
歸並到b [1 2 3 4 5 6 7 8]
復制到a [1 2 3 4 5 6 7 8]
圖14-8 歸並排序的例子
另一種二路歸並排序演算法是這樣的：首先將每兩個相鄰的大小為1的子序列歸並，然後對上一次歸並所得到的大小為2的子序列進行相鄰歸並，如此反復，直至最後歸並到一個序列，歸並過程完成。通過輪流地將元素從a 歸並到b 並從b 歸並到a，可以虛擬地消除復制過程。二路歸並排序演算法見程序1 4 - 3。
程序14-3 二路歸並排序
template
void MergeSort(T a[], int n)
{// 使用歸並排序演算法對a[0:n-1] 進行排序
T *b = new T [n];
int s = 1; // 段的大小
while (s < n) {
MergePass(a, b, s, n); // 從a歸並到b
s += s;
MergePass(b, a, s, n); // 從b 歸並到a
s += s;
}
}
為了完成排序代碼，首先需要完成函數M e rg e P a s s。函數M e rg e P a s s（見程序1 4 - 4）僅用來確定欲歸並子序列的左端和右端，實際的歸並工作由函數M e rg e (見程序1 4 - 5 )來完成。函數M e rg e要求針對類型T定義一個操作符< =。如果需要排序的數據類型是用戶自定義類型，則必須重載操作符< =。這種設計方法允許我們按元素的任一個域進行排序。重載操作符< =的目的是用來比較需要排序的域。
程序14-4 MergePass函數
template
void MergePass(T x[], T y[], int s, int n)
{// 歸並大小為s的相鄰段
int i = 0;
while (i <= n - 2 * s) {
// 歸並兩個大小為s的相鄰段
Merge(x, y, i, i+s-1, i+2*s-1);
i = i + 2 * s;
}
// 剩下不足2個元素
if (i + s < n) Merge(x, y, i, i+s-1, n-1);
else for (int j = i; j <= n-1; j++)
// 把最後一段復制到y
y[j] = x[j];
}
程序14-5 Merge函數
template
void Merge(T c[], T d[], int l, int m, int r)
{// 把c[l:m]] 和c[m:r] 歸並到d [ l : r ] .
int i = l, // 第一段的游標
j = m+1, // 第二段的游標
k = l; // 結果的游標
/ /只要在段中存在i和j，則不斷進行歸並
while ((i <= m) && (j <= r))
if (c[i] <= c[j]) d[k++] = c[i++];
else d[k++] = c[j++];
// 考慮餘下的部分
if (i > m) for (int q = j; q <= r; q++)
d[k++] = c[q];
else for (int q = i; q <= m; q++)
d[k++] = c[q];
}
自然歸並排序（natural merge sort）是基本歸並排序（見程序1 4 - 3）的一種變化。它首先對輸入序列中已經存在的有序子序列進行歸並。例如，元素序列[ 4，8，3，7，1，5，6，2 ]中包含有序的子序列[ 4，8 ]，[ 3，7 ]，[ 1，5，6 ]和[ 2 ]，這些子序列是按從左至右的順序對元素表進行掃描而產生的，若位置i 的元素比位置i+ 1的元素大，則從位置i 進行分割。對於上面這個元素序列，可找到四個子序列，子序列1和子序列2歸並可得[ 3 , 4 , 7 , 8 ]，子序列3和子序列4歸並可得[ 1 , 2 , 5 , 6 ]，最後，歸並這兩個子序列得到[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。因此，對於上述元素序列，僅僅使用了兩趟歸並，而程序1 4 - 3從大小為1的子序列開始，需使用三趟歸並。作為一個極端的例子，假設輸入的元素序列已經排好序並有n個元素，自然歸並排序法將准確地識別該序列不必進行歸並排序，但程序1 4 - 3仍需要進行[ l o g2 n] 趟歸並。因此自然歸並排序將在(n) 的時間內完成排序。而程序1 4 - 3將花費(n l o gn) 的時間。
❸ 演算法導論中，為什麼合並排序的遞歸樹的高度為lgn
符號問題，這里的lg就是指log2，你的理解是正確的！在計算機科學中有些符號的使用跟我們在數學中使用的有區別。比如有時候log用來表示自然對數(以e為底數)。希望對你有幫助！
❹ 歸並排序
先考慮一個簡單的問題：如何在線性的時間內將兩個有序隊列合並為一個有序隊列（並輸出）？
A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
看上面的例子，AB兩個序列都是已經有序的了。在給出數據已經有序的情況下，我們會發現很多神奇的事，比如，我們將要輸出的第一個數一定來自於這兩個序列各自最前面的那個數。兩個數都是1，那麼我們隨便取出一個（比如A隊列的那個1）並輸出：
A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1
注意，我們取出了一個數，在原數列中刪除這個數。刪除操作是通過移動隊首指針實現的，否則復雜度就高了。
現在，A隊列打頭的數變成3了，B隊列的隊首仍然是1。此時，我們再比較3和1哪個大並輸出小的那個數：
A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1 1
接下來的幾步如下：
A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9
B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ……
輸出：1 1 2 輸出：1 1 2 3 輸出：1 1 2 3 5 輸出：1 1 2 3 5 7
我希望你明白了這是怎麼做的。這個做法顯然是正確的，復雜度顯然是線性。
歸並排序(Merge Sort)將會用到上面所說的合並操作。給出一個數列，歸並排序利用合並操作在O(nlogn)的時間內將數列從小到大排序。歸並排序用的是分治(Divide and Conquer)的思想。首先我們把給出的數列平分為左右兩段，然後對兩段數列分別進行排序，最後用剛才的合並演算法把這兩段（已經排過序的）數列合並為一個數列。有人會問「對左右兩段數列分別排序時用的什麼排序」么？答案是：用歸並排序。也就是說，我們遞歸地把每一段數列又分成兩段進行上述操作。你不需要關心實際上是怎麼操作的，我們的程序代碼將遞歸調用該過程直到數列不能再分（只有一個數）為止。
初看這個演算法時有人會誤以為時間復雜度相當高。我們下面給出的一個圖將用非遞歸的眼光來看歸並排序的實際操作過程，供大家參考。我們可以藉助這個圖證明，歸並排序演算法的時間復雜度為O(nlogn)。
[3] [1] [4] [1] [5] [9] [2] [7]
\ / \ / \ / \ /
[1 3] [1 4] [5 9] [2 7]
\ / \ /
[1 1 3 4] [2 5 7 9]
\ /
[1 1 2 3 4 5 7 9]
上圖中的每一個「 \ / 」表示的是上文所述的線性時間合並操作。上圖用了4行來圖解歸並排序。如果有n個數，表示成上圖顯然需要O(logn)行。每一行的合並操作復雜度總和都是O(n)，那麼logn行的總復雜度為O(nlogn)。這相當於用遞歸樹的方法對歸並排序的復雜度進行了分析。假設，歸並排序的復雜度為T(n)，T(n)由兩個T(n/2)和一個關於n的線性時間組成，那麼T(n)=2*T(n/2)+O(n)。不斷展開這個式子我們可以同樣可以得到T(n)=O(nlogn)的結論，你可以自己試試。如果你能在線性的時間里把分別計算出的兩組不同數據的結果合並在一起，根據T(n)=2*T(n/2)+O(n)=O(nlogn)，那麼我們就可以構造O(nlogn)的分治演算法。這個結論後面經常用。我們將在計算幾何部分舉一大堆類似的例子。
如果你第一次見到這么詭異的演算法，你可能會對這個感興趣。分治是遞歸的一種應用。這是我們第一次接觸遞歸運算。下面說的快速排序也是用的遞歸的思想。遞歸程序的復雜度分析通常和上面一樣，主定理(Master Theory)可以簡化這個分析過程。主定理和本文內容離得太遠，我們以後也不會用它，因此我們不介紹它，大家可以自己去查。有個名詞在這里的話找學習資料將變得非常容易，我最怕的就是一個東西不知道叫什麼名字，半天找不到資料。
歸並排序有一個有趣的副產品。利用歸並排序能夠在O(nlogn)的時間里計算出給定序列里逆序對的個數。你可以用任何一種平衡二叉樹來完成這個操作，但用歸並排序統計逆序對更方便。我們討論逆序對一般是說的一個排列中的逆序對，因此這里我們假設所有數不相同。假如我們想要數1, 6, 3, 2, 5, 4中有多少個逆序對，我們首先把這個數列分為左右兩段。那麼一個逆序對只可能有三種情況：兩個數都在左邊，兩個數都在右邊，一個在左一個在右。在左右兩段分別處理完後，線性合並的過程中我們可以順便算出所有第三種情況的逆序對有多少個。換句話說，我們能在線性的時間里統計出A隊列的某個數比B隊列的某個數大有多少種情況。
A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6
B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ……
輸出： 輸出：1 輸出：1 2 輸出：1 2 3 輸出：1 2 3 4
每一次從B隊列取出一個數時，我們就知道了在A隊列中有多少個數比B隊列的這個數大，它等於A隊列現在還剩的數的個數。比如，當我們從B隊列中取出2時，我們同時知道了A隊列的3和6兩個數比2大。在合並操作中我們不斷更新A隊列中還剩幾個數，在每次從B隊列中取出一個數時把當前A隊列剩的數目加進最終答案里。這樣我們算出了所有「大的數在前一半，小的數在後一半」的情況，其餘情況下的逆序對在這之前已經被遞歸地算過了。
============================華麗的分割線============================
堆排序(Heap Sort)利用了堆(Heap)這種數據結構（什麼是堆？）。堆的插入操作是平均常數的，而刪除一個根節點需要花費O(log n)的時間。因此，完成堆排序需要線性時間建立堆（把所有元素依次插入一個堆），然後用總共O(nlogn)的時間不斷取出最小的那個數。只要堆會搞，堆排序就會搞。堆在那篇日誌里有詳細的說明，因此這里不重復說了。
============================華麗的分割線============================
快速排序(Quick Sort)也應用了遞歸的思想。我們想要把給定序列分成兩段，並對這兩段分別進行排序。一種不錯的想法是，選取一個數作為「關鍵字」，並把其它數分割為兩部分，把所有小於關鍵字的數都放在關鍵字的左邊，大於關鍵字的都放在右邊，然後遞歸地對左邊和右邊進行排序。把該區間內的所有數依次與關鍵字比較，我們就可以在線性的時間里完成分割的操作。完成分割操作有很多有技巧性的實現方法，比如最常用的一種是定義兩個指針，一個從前往後找找到比關鍵字大的，一個從後往前找到比關鍵字小的，然後兩個指針對應的元素交換位置並繼續移動指針重復剛才的過程。這只是大致的方法，具體的實現還有很多細節問題。快速排序是我們最常用的代碼之一，網上的快速排序代碼五花八門，各種語言，各種風格的都有。大家可以隨便找一個來看看，我說過了我們講演算法但不講如何實現。NOIp很簡單，很多人NOIp前就背了一個快速排序代碼就上戰場了。當時我把快速排序背完了，抓緊時間還順便背了一下歷史，免得晚上聽寫又不及格。
不像歸並排序，快速排序的時間復雜度很難計算。我們可以看到，歸並排序的復雜度最壞情況下也是O(nlogn)的，而快速排序的最壞情況是O(n^2)的。如果每一次選的關鍵字都是當前區間里最大（或最小）的數，那麼這樣將使得每一次的規模只減小一個數，這和插入排序、選擇排序等平方級排序沒有區別。這種情況不是不可能發生。如果你每次選擇關鍵字都是選擇的該區間的第一個數，而給你的數據恰好又是已經有序的，那你的快速排序就完蛋了。顯然，最好情況是每一次選的數正好就是中位數，這將把該區間平分為兩段，復雜度和前面討論的歸並排序一模一樣。根據這一點，快速排序有一些常用的優化。比如，我們經常從數列中隨機取一個數當作是關鍵字（而不是每次總是取固定位置上的數），從而盡可能避免某些特殊的數據所導致的低效。更好的做法是隨機取三個數並選擇這三個數的中位數作為關鍵字。而對三個數的隨機取值反而將花費更多的時間，因此我們的這三個數可以分別取數列的頭一個數、末一個數和正中間那個數。另外，當遞歸到了一定深度發現當前區間里的數只有幾個或十幾個時，繼續遞歸下去反而費時，不如返回插入排序後的結果。這種方法同時避免了當數字太少時遞歸操作出錯的可能。
下面我們證明，快速排序演算法的平均復雜度為O(nlogn)。不同的書上有不同的解釋方法，這里我選用演算法導論上的講法。它更有技巧性一些，更有趣一些，需要轉幾個彎才能想明白。
看一看快速排序的代碼。正如我們提到過的那種分割方法，程序在經過若干次與關鍵字的比較後才進行一次交換，因此比較的次數比交換次數更多。我們通過證明一次快速排序中元素之間的比較次數平均為O(nlogn)來說明快速排序演算法的平均復雜度。證明的關鍵在於，我們需要算出某兩個元素在整個演算法過程中進行過比較的概率。
我們舉一個例子。假如給出了1到10這10個數，第一次選擇關鍵字7將它們分成了{1,2,3,4,5,6}和{8,9,10}兩部分，遞歸左邊時我們選擇了3作為關鍵字，使得左部分又被分割為{1,2}和{4,5,6}。我們看到，數字7與其它所有數都比較過一次，這樣才能實現分割操作。同樣地，1到6這6個數都需要與3進行一次比較（除了它本身之外）。然而，3和9決不可能相互比較過，2和6也不可能進行過比較，因為第一次出現在3和9，2和6之間的關鍵字把它們分割開了。也就是說，兩個數A(i)和A(j)比較過，當且僅當第一個滿足A(i)<=x<=A(j)的關鍵字x恰好就是A(i)或A(j) （假設A(i)比A(j)小）。我們稱排序後第i小的數為Z(i)，假設i<j，那麼第一次出現在Z(i)和Z(j)之間的關鍵字恰好就是Z(i)或Z(j)的概率為2/(j-i+1)，這是因為當Z(i)和Z(j)之間還不曾有過關鍵字時，Z(i)和Z(j)處於同一個待分割的區間，不管這個區間有多大，不管遞歸到哪裡了，關鍵字的選擇總是隨機的。我們得到，Z(i)和Z(j)在一次快速排序中曾經比較過的概率為2/(j-i+1)。
現在有四個數，2,3,5,7。排序時，相鄰的兩個數肯定都被比較過，2和5、3和7都有2/3的概率被比較過，2和7之間被比較過有2/4的可能。也就是說，如果對這四個數做12次快速排序，那麼2和3、3和5、5和7之間一共比較了12*3=36次，2和5、3和7之間總共比較了8*2=16次，2和7之間平均比較了6次。那麼，12次排序中總的比較次數期望值為36+16+6=58。我們可以計算出單次的快速排序平均比較了多少次：58/12=29/6。其實，它就等於6項概率之和，1+1+1+2/3+2/3+2/4=29/6。這其實是與期望值相關的一個公式。
同樣地，如果有n個數，那麼快速排序平均需要的比較次數可以寫成下面的式子。令k=j-i，我們能夠最終得到比較次數的期望值為O(nlogn)。
這里用到了一個知識：1+1/2+1/3+...+1/n與log n增長速度相同，即∑(1/n)=Θ(log n)。它的證明放在本文的最後。
在三種O(nlogn)的排序演算法中，快速排序的理論復雜度最不理想，除了它以外今天說的另外兩種演算法都是以最壞情況O(nlogn)的復雜度進行排序。但實踐上看快速排序效率最高（不然為啥叫快速排序呢），原因在於快速排序的代碼比其它同復雜度的演算法更簡潔，常數時間更小。
快速排序也有一個有趣的副產品：快速選擇給出的一些數中第k小的數。一種簡單的方法是使用上述任一種O(nlogn)的演算法對這些數進行排序並返回排序後數組的第k個元素。快速選擇(Quick Select)演算法可以在平均O(n)的時間完成這一操作。它的最壞情況同快速排序一樣，也是O(n^2)。在每一次分割後，我們都可以知道比關鍵字小的數有多少個，從而確定了關鍵字在所有數中是第幾小的。我們假設關鍵字是第m小。如果k=m，那麼我們就找到了答案——第k小元素即該關鍵字。否則，我們遞歸地計算左邊或者右邊：當k<m時，我們遞歸地尋找左邊的元素中第k小的；當k>m時，我們遞歸地尋找右邊的元素中第k-m小的數。由於我們不考慮所有的數的順序，只需要遞歸其中的一邊，因此復雜度大大降低。復雜度平均線性，我們不再具體證了。
還有一種演算法可以在最壞O(n)的時間里找出第k小元素。那是我見過的所有演算法中最沒有實用價值的演算法。那個O(n)只有理論價值。
============================華麗的分割線============================
我們前面證明過，僅僅依靠交換相鄰元素的操作，復雜度只能達到O(n^2)。於是，人們嘗試交換距離更遠的元素。當人們發現O(nlogn)的排序演算法似乎已經是極限的時候，又是什麼制約了復雜度的下界呢？我們將要討論的是更底層的東西。我們仍然假設所有的數都不相等。
我們總是不斷在數與數之間進行比較。你可以試試，只用4次比較絕對不可能給4個數排出順序。每多進行一次比較我們就又多知道了一個大小關系，從4次比較中一共可以獲知4個大小關系。4個大小關系共有2^4=16種組合方式，而4個數的順序一共有4!=24種。也就是說，4次比較可能出現的結果數目不足以區分24種可能的順序。更一般地，給你n個數叫你排序，可能的答案共有n!個，k次比較只能區分2^k種可能，於是只有2^k>=n!時才有可能排出順序。等號兩邊取對數，於是，給n個數排序至少需要log2(n!)次。注意，我們並沒有說明一定能通過log2(n!)次比較排出順序。雖然2^5=32超過了4!，但這不足以說明5次比較一定足夠。如何用5次比較確定4個數的大小關系還需要進一步研究。第一次例外發生在n=12的時候，雖然2^29>12!，但現已證明給12個數排序最少需要30次比較。我們可以證明log(n!)的增長速度與nlogn相同，即log(n!)=Θ(nlogn)。這是排序所需要的最少的比較次數，它給出了排序復雜度的一個下界。log(n!)=Θ(nlogn)的證明也附在本文最後。
這篇日誌的第三題中證明log2(N)是最優時用到了幾乎相同的方法。那種「用天平稱出重量不同的那個球至少要稱幾次」一類題目也可以用這種方法來解決。事實上，這里有一整套的理論，它叫做資訊理論。資訊理論是由香農(Shannon)提出的。他用對數來表示信息量，用熵來表示可能的情況的隨機性，通過運算可以知道你目前得到的信息能夠怎樣影響最終結果的確定。如果我們的信息量是以2為底的，那資訊理論就變成信息學了。從根本上說，計算機的一切信息就是以2為底的信息量(bits=binary digits)，因此我們常說香農是數字通信之父。資訊理論和熱力學關系密切，比如熵的概念是直接從熱力學的熵定義引申過來的。和這個有關的東西已經嚴重偏題了，這里不說了，有興趣可以去看《資訊理論與編碼理論》。我對這個也很有興趣，半懂不懂的，很想了解更多的東西，有興趣的同志不妨加入討論。物理學真的很神奇，利用物理學可以解決很多純數學問題，我有時間的話可以舉一些例子。我他媽的為啥要選文科呢。
後面將介紹的三種排序是線性時間復雜度，因為，它們排序時根本不是通過互相比較來確定大小關系的。
附1：∑(1/n)=Θ(log n)的證明
首先我們證明，∑(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/2，使得兩個1/2加起來湊成一個1；再把1/5,1/6和1/7全部變成1/4，這樣四個1/4加起來又是一個1。我們把所有1/2^k的後面2^k-1項全部擴大為1/2^k，使得這2^k個分式加起來是一個1。現在，1+1/2+...+1/n裡面產生了幾個1呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的擴大後原式各項總和為log n。O(logn)是∑(1/n)的復雜度上界。
然後我們證明，∑(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/4，使得兩個1/4加起來湊成一個1/2；再把1/5,1/6和1/7全部變成1/8，這樣四個1/8加起來又是一個1/2。我們把所有1/2^k的前面2^k-1項全部縮小為1/2^k，使得這2^k個分式加起來是一個1/2。現在，1+1/2+...+1/n裡面產生了幾個1/2呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的縮小後原式各項總和為1/2*logn。Ω(logn)是∑(1/n)的復雜度下界。
附2：log(n!)=Θ(nlogn)的證明
首先我們證明，log(n!)=O(nlogn)。顯然n!<n^n，兩邊取對數我們得到log(n!)<log(n^n)，而log(n^n)就等於nlogn。因此，O(nlogn)是log(n!)的復雜度上界。
然後我們證明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)....1，把前面一半的因子全部縮小到n/2，後面一半因子全部捨去，顯然有n!>(n/2)^(n/2)。兩邊取對數，log(n!)>(n/2)log(n/2)，後者即Ω(nlogn)。因此，Ω(nlogn)是log(n!)的復雜度下界。
今天寫到這里了，大家幫忙校對哦
Matrix67原創
轉貼請註明出處
❺ 歸並排序
歸並排序 （Merge sort，或mergesort），是創建在歸並操作上的一種有效的排序演算法，效率為 。1945 年由約翰·馮·諾伊曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。
這裡面提到了兩個概念，分別是 分治（法） 和 遞歸 ，它們是什麼呢？
分治法（Divide and Conquer）是基於多路分支遞歸求和的一種很重要的演算法範式。字面上的解釋是「分而治之」，就是把一個復雜的問題分成兩個或更多凱宏的相同或相似的子問題，再把子問題分成更小的子問題，直到最後子問題可以簡單的直接求解，原問題的解就是子問題的解的合並。這個技巧是很多高效演算法的基礎，如排序演算法中的快速排序和歸並排序，傅立葉變換中的快速傅立葉變換…
分治模式在每層遞歸時都有三個步驟：
遞歸（英語：Recursion），又譯為遞回， 在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況，如函數的定義中使用函數自身的方法。遞歸一詞還較常用於描述以自相似方法重復事物的過程。 例如，當兩面鏡子相互之間睜叢近似平行時，鏡中嵌套的圖像是以無限遞歸的形式出現的。 也可以理解為自我復制的過程。
歸並排序演算法完全遵循分治模式，直觀上，其操作步驟如下：
當待排序的序列長度為 1 時，遞歸「開始回升」，在這種情況下無須作任何工作，因為長度為 1 的每個序列都已排好序。
MERGE 的詳細工作過程如下：
我們必須證明第 12～17 行 for 循環的第一次迭代之前該循環不變式成立，且在該循環的每次迭代時保持該不變式，當循環終止時，該不變式須提供一種有用的性質來證明演算法的正確性。
前面我們分析了分治演算法的過程，我們可以把 MERGE 作為歸並排序演算法中的一個子程序來用。
上面已經對分治法做悉孫櫻了正確性證明，歸並排序的正確性不言而喻。
分治演算法運行時間的遞歸式來自基本模式的三個步驟，即分解、解決和合並。假設 T(n) 是規模為 n 的一個問題的運行時間。若問題規模足夠小，如對某個常量 c，n≤c，則直接求解需要常量時間，可以將其寫成 O(1)。假設把原問題分解成 a 個子問題，每個子問題的規模是原問題的 1/b。為了求解一個規模為 n/b 的子問題，需要 T(n/b) 的時間，所以需要 aT(n/b) 的時間來求解 a 個子問題。如果分解問題成子問題需要時間 D(n)，合並子問題的解成原問題的解需要時間 C(n)，那麼得到遞歸式：
現在我們來討論歸並排序。假定問題規模是 2 的冪（不是 2 的冪時也能正確地工作），歸並排序一個元素的時間是常量，當有 n>1 個元素時，分解運行的時間如下：
為了分析歸並排序，我們可以將 D(n) 與 C(n) 相加，即把一個 函數與另一個 函數相加，得到的和是一個 n 的線性函數，即 。把它與來自「解決」步驟的項 2T(n/2) 相加，將給出歸並排序的最壞情況的運行時間
將遞歸式重寫，得到
其中，常量 c 代表求解規模為 1 的問題所需要的時間以及在分解步驟與合並步驟處理每個數組元素所需要的時間。(相同的常量一般不可能剛好即代表求解規模為 1 的問題的時間又代表分解步驟與合並步驟處理每個數組元素的時間。通過假設 c 為這兩個時間的較大者並認為我們的遞歸式將給出運行時間的一個上界，或者通過假設 c 為這兩個時間的較小者並認為我們的遞歸式將給出運行時間的下界，我們可以暫時迴避這個問題。兩個界的階都是 ，合在一起將給出運行時間為 )。
求解遞歸式的過程如下圖所示：
可以看出，樹根 cn 通過遞歸分解，直到規模降為 1 後，每個子問題只要代價 c。分解步驟一共經歷了 次，即樹高為 層，每層的代價為 cn，因此總代價為 。
上面我們已經知道了，總代價為 ，忽略低階項和常量 c，歸並排序的時間復雜度為 O(nlogn)。
歸並排序的合並函數，在合並兩個有序數組為一個有序數組時，需要藉助額外的存儲空間，但是這個申請額外的內存空間，會在合並完成之後釋放，因此，在任意時刻，只會有一個臨時的內存空間在使用，臨時內存空間最大也不會超過 n 個數據的大小，所以空間復雜度是 O(n)。
Javascript 遞歸版
Go
迭代版
遞歸版