合並排序演算法遞歸

1. 歸並排序的程序

歸並排序
當初學習鏈表的時候，我們都曾經做過將兩個有序鏈表合成一個有序鏈表的練習。那時我們就知道了歸並的特點就是，將分段有序的序列合成整體有序的序列。在內部排序中，歸並的地位並不十分重要，主要是因為附加的O(n)的儲存空間；但是，歸並卻是外部排序的不二法門——我們只能用內排得到分段有序的序列，為了得到最後的有序序列，必須使用歸並的方法。
迭代的2路歸並排序
2路歸並是最簡單的，並且單純對內存中數據操作2路的往往是最好的（比如平衡樹，AVL樹經常優於m叉的平衡樹）。所謂的迭代就是先歸並len＝1的N個序列，然後是len＝2的N/2個序列，len＝4的N/4個序列……最後歸並2個序列就完成了。實際寫的時候，需要一個和原來序列一樣大小的臨時數組。執行偶數次「一趟歸並」能夠使得最後的結果保存在原來的數組中。
//迭代2路歸並排序及其所需的子程序
template <class T>
void Merge(T S[], T D[], int l, int m, int n, int& KCN, int& RMN)
{
//S[]源表，D[]歸並後的表，l源表第一個段的起始序號，m源表第二個段的起始序號，n源表的長度
int i = l, j = m, k = l;//i第一段的指針，j第二段的指針，k目的表指針
for (; i < m && j < n; RMN++, k++)
if (++KCN && S[i] > S[j]) { D[k] = S[j]; j++; } else { D[k] = S[i]; i++; }
if (i < m)
for (; i < m; i++, k++, RMN++) D[k] = S[i];
else
for (; j < n; j++, k++, RMN++) D[k] = S[j];
}
template <class T>
void MergePass(T S[], T D[], int len, int N, int& KCN, int& RMN)
{
int i = 0;
for (; i+2*len < N; i += 2*len) Merge(S, D, i, i+len, i+2*len, KCN, RMN);
if (i+len < N) Merge(S, D, i, i+len, N, KCN, RMN);//剩餘多於一個len，再做一次歸並
else for (; i < N; i++, RMN++) D[i] = S[i];//少於等於一個len，直接復制
}
template <class T>
void MergeSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
T* temp = new T[N]; int len = 1;
while (len < N)//固定執行偶數次MergePass，最後的結果在原來的數組里
{
MergePass(a, temp, len, N, KCN, RMN); len *= 2;
MergePass(temp, a, len, N, KCN, RMN); len *= 2;
}
delete []temp;
}
測試結果，直接取N＝100000：
Sort ascending N=100000 TimeSpared: 210ms
KCN=877968 KCN/N=8.77968 KCN/N^2=8.77968e-005KCN/NlogN=0.528589
RMN=1800000 RMN/N=18 RMN/N^2=0.00018 RMN/NlogN=1.08371
Sort randomness N=100000 TimeSpared: 230ms
KCN=1529317 KCN/N=15.2932 KCN/N^2=0.000152932KCN/NlogN=0.920741
RMN=1800000 RMN/N=18 RMN/N^2=0.00018 RMN/NlogN=1.08371
Sort descending N=100000 TimeSpared: 201ms
KCN=815024 KCN/N=8.15024 KCN/N^2=8.15024e-005KCN/NlogN=0.490693
RMN=1800000 RMN/N=18 RMN/N^2=0.00018 RMN/NlogN=1.08371
可以看到RMN是個定值，RMN/N的值是不小於log2N的最小偶數，有興趣比較一下N＝1和N＝2的差異就明白了。和快排（N＝100000，亂序）相比，雖然歸並的KCN和RMN都要少一些，但快排的速度還是要比歸並排序快一倍（說明歸並的額外動作多了一些），這個現象的確值得我們思考，這也是我加上KCN和RMN統計的一個意外收獲——歸並比快排慢不是因為KCN和RMN比快排多，而是一些額外的東西。
仔細分析就會發現，歸並的多餘時耗主要在小段歸並上，如果我們用在N非常小的時候最為高效的直插來代替此時的歸並，應該能帶來效率的提升。如下面的常式，首先用直插來產生len＝32的初始歸並段，然後再歸並：
template <class T>
void MergeSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
T* temp = new T[N]; int len = 32, i, j, k;
//分段進行直插排序，生成初始為len長的歸並段

for (k = 1; k < N; k += len)
{
for (i = k; i < k+len-1 && i < N; i++)//為了避免i<N這個判斷，可以對原序列剩餘小於len的序列另寫一個直插
{
T temp = a[i]; RMN++;
for (j = i; j >= k && ++KCN && temp < a[j - 1]; j--) { a[j] = a[j - 1]; RMN++; }
a[j] = temp; RMN++;
}
}

while (len < N)//固定執行偶數次MergePass，最後的結果在原來的數組里
{
MergePass(a, temp, len, N, KCN, RMN); len *= 2;
MergePass(temp, a, len, N, KCN, RMN); len *= 2;
}
delete []temp;
}
測試結果：
Sort ascending N=100000 TimeSpared: 160ms
KCN=724843 KCN/N=7.24843 KCN/N^2=7.24843e-005KCN/NlogN=0.436399
RMN=1393750 RMN/N=13.9375 RMN/N^2=0.000139375RMN/NlogN=0.839121
Sort randomness N=100000 TimeSpared: 160ms
KCN=2009896 KCN/N=20.099 KCN/N^2=0.00020099 KCN/NlogN=1.21008
RMN=2166630 RMN/N=21.6663 RMN/N^2=0.000216663RMN/NlogN=1.30444
Sort descending N=100000 TimeSpared: 170ms
KCN=2115024 KCN/N=21.1502 KCN/N^2=0.000211502KCN/NlogN=1.27337
RMN=2943750 RMN/N=29.4375 RMN/N^2=0.000294375RMN/NlogN=1.77231
對於N=100000亂序排序減少了70ms，應該說是比較滿意的。
遞歸的2路表歸並排序
很自然的，除了從len＝1開始兩兩歸並外，還可以從len＝N開始，1/2分裂成左右序列分別歸並排序，這是一個遞歸過程。如果我們仔細的觀察這個遞歸，會發現這和前面的迭代是一樣的（N＝2k的情況）。遞歸帶來的好處是可以方便的使用靜態鏈表（非常容易實現表頭的動態產生和消亡），如果我們不使用鏈表，研究遞歸的歸並也沒什麼意思。
//遞歸的2路表歸並排序及其所需子程序
template <class T>
int ListMerge(T a[], int link[], int head1, int head2, int& KCN)
{
int k, head, i = head1, j = head2;//i,j為兩個鏈表的游標，k為結果鏈表游標，結果鏈表的表頭為head
//因為沒有表頭節點，表頭需單獨處理
if (++KCN && a[i] > a[j]) { head = j; k = j; j = link[j]; }
else { head = i; k = i; i = link[i]; }
while (i != -1 && j != -1)
{
if (++KCN && a[i] > a[j]) { link[k] = j; k = j; j = link[j]; }
else { link[k] = i; k = i; i = link[i]; }
}
if (i == -1) link[k] = j;//i鏈檢測完，j鏈接上
else link[k] = i;//否則，i鏈接上
return head;//返回頭指針
}
template <class T>
int rMergeSort(T a[], int link[], int low, int high, int& KCN)
{
if (low >= high) return low;
int mid = (low + high)/2;
return ListMerge(a, link, rMergeSort(a, link, low, mid, KCN), rMergeSort(a, link, mid+1, high, KCN), KCN);
}
template <class T>
void ListMergeSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0; int i, cur, pre;
int* link = new int[N];
for (i = 0; i < N; i++) link[i] = -1;
cur = rMergeSort(a, link, 0, N - 1, KCN);
for (i = 0; i < N; i++)//重排
{
while (cur < i) cur = link[cur];
pre = link[cur];
if (cur != i)
{
swap(a[i], a[cur]); RMN += 3;
link[cur] = link[i]; link[i] = cur;
}
cur = pre;
}
delete []link;
}
這里的rMergeSort可以算是個間接遞歸的例子，注意遞歸是如何自動完成表頭的創建與回收的——的確是個很精巧的實現，如果反過來用迭代來實現，將會很麻煩。
測試結果：
Sort ascending N=100000 TimeSpared: 50ms
KCN=853904 KCN/N=8.53904 KCN/N^2=8.53904e-005KCN/NlogN=0.514101
RMN=0 RMN/N=0 RMN/N^2=0 RMN/NlogN=0
Sort randomness N=100000 TimeSpared: 350ms
KCN=1509031 KCN/N=15.0903 KCN/N^2=0.000150903KCN/NlogN=0.908527
RMN=299973 RMN/N=2.99973 RMN/N^2=2.99973e-005RMN/NlogN=0.180602
Sort descending N=100000 TimeSpared: 70ms
KCN=815024 KCN/N=8.15024 KCN/N^2=8.15024e-005KCN/NlogN=0.490693
RMN=150000 RMN/N=1.5 RMN/N^2=1.5e-005 RMN/NlogN=0.090309
少有的在正序和逆序都有上佳表現的排序方法，但就其平均性能來說，並不十分優秀。

2. 歸並排序演算法：用兩路歸並演算法，實現N個無素的排序

合並排序（MERGE SORT）是又一類不同的排序方法，合並的含義就是將兩個或兩個以上的有序數據序列合並成一個新的有序數據序列，因此它又叫歸並演算法。它的基本思想就是假設數組A有N個元素，那麼可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然後再兩兩合並，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合並，如此重復，值得得到一個長度為N的有序數據序列為止，這種排序方法稱為2—路合並排序。

例如數組A有7個數據，分別是： 49 38 65 97 76 13 27，那麼採用歸並排序演算法的操作過程如圖7所示：

初始值 [49] [38] [65] [97] [76] [13] [27]

看成由長度為1的7個子序列組成

第一次合並之後 [38 49] [65 97] [13 76] [27]

看成由長度為1或2的4個子序列組成

第二次合並之後 [38 49 65 97] [13 27 76]

看成由長度為4或3的2個子序列組成

第三次合並之後 [13 27 38 49 65 76 97]

合並演算法的核心操作就是將一維數組中前後相鄰的兩個兩個有序序列合並成一個有序序列。合並演算法也可以採用遞歸演算法來實現，形式上較為簡單,但實用性很差。合並演算法的合並次數是一個非常重要的量,根據計算當數組中有3到4個元素時,合並次數是2次,當有5到8個元素時,合並次數是3次,當有9到16個元素時,合並次數是4次，按照這一規律,當有N個子序列時可以推斷出合並的次數是X(2 >=N,符合此條件的最小那個X)。
其時間復雜度為：O(nlogn).所需輔助存儲空間為：O(n)

歸並演算法如下：
long merge(long *A,long p,long q,long r)
{
long n1,n2,i,j,k;
long *L,*R;
n1=q-p+1;
n2=r-q;
L=(long *)malloc((n1+2)*sizeof(long));
R=(long *)malloc((n2+2)*sizeof(long));
for(i=1;i<=n1;i++)
L=A[p+i-1];
for(j=1;j<=n2;j++)
R[j]=A[q+j];
L[n1+1]=R[n2+1]=RAND_MAX;
i=j=1;
for(k=p;k<=r;k++)
{
if(L<=R[j])
{
A[k]=L;
i++;
}
else
{
A[k]=R[j];
j++;
}
}
free(L);
free(R);
return 0;
}

long mergesort(long *A,long p,long r)
{
long q;
if(p<r)
{
q=(p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
return 0;
}

3. 歸並排序（Merge Sort）

歸並排序 是最高效的排序演算法之一。該排序演算法的時間復雜度是 O(log n) ，歸並排序是由分割和合並組成的。將一個比較大的問題分割成若干容易解決的小問題，然後進行合並，得到一個最終的結果。歸並排序的口訣就是先分割，後合並。

舉個例子，假定你手中有如下一摞卡牌：

排序演算法的排序過程大致是這樣的：
1，首先，將這一摞牌分成兩半，這樣就得到了兩摞無序的卡牌。

1，最後，以和分割相反的順序，將每一摞卡牌合並。在每一次合並的過程中，將數據按照規則進行排序。由於每一小摞的卡牌都已經有序，在合並的時候會比較容易些。

首先，先將數組分成兩半：

將數組分割一次遠遠不夠，需要遞歸調用分割函數，直到不能在分割為止。這樣的話，每一個子部分都只包含一個元素。按照這種思路，我們將 mergeSort 更新至如下所示：

這里有兩個變動點：
1，對函數進行了遞歸調用，在數組中有且只有一個元素時，停止遞歸調用。
2，對原數組的左右子數組都調用 mergeSort 。

如上代碼在能通過編譯之前，仍然還有很多事情去做。現在已經完成了數組分割部分，是時候去關注於合並了。

合並左右子數組是該演算法的最後一步。為了更演算法更明了一些，單獨創建一個 merge 方法。

merge 方法的職責僅僅是 將兩個將兩個有序的數組合並成一個有序的數組。在 mergeSort 函數中，增加以下方法：

最後附上本文的相關代碼 DataAndAlgorim

參考鏈接 《Data Structures & Algorithms in Swift》

4. 排序演算法有多少種

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般來說有升序排列和降序排列2種排序，在演算法中有8中基本排序：
(1)冒泡排序；
(2)選擇排序；
(3)插入排序；
(4)希爾排序；
(5)歸並排序；
(6)快速排序；
(7)基數排序；
(8)堆排序；
(9)計數排序；
(10)桶排序。
插入排序
插入排序演算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的後面，因此插入該元素後並未改變原序列的前後順序。我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。
冒泡排序
冒泡排序演算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和演算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重復進行上述計算，直至完成第(n一1)個和第n個記錄的關鍵字之間的比較，此後，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴格的穩定排序演算法，它不改變序列中相同元素之間的相對位置關系。
選擇排序
選擇排序演算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置即可；以此類推，重復進行「最小元素」的選擇，直至完成第(n-1)個位置的元素選擇，則第n個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同於冒泡法的細節。舉例說明：序列58539．我們知道第一遍選擇第1個元素「5」會和元素「3」交換，那麼原序列中的兩個相同元素「5」之間的前後相對順序就發生了改變。因此，我們說選擇排序不是穩定的排序演算法，它在計算過程中會破壞穩定性。
快速排序
快速排序的基本思想是:通過一趟排序演算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分後的這兩塊序列的元素分別再次實行快速排序演算法，排序實現的整個過程可以是遞歸的來進行調用，最終能夠實現將所需排序的無序序列元素變為一個有序的序列。
歸並排序
歸並排序演算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規則進行排序為長序列。歸並排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合並得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列；將上述步驟重復操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該演算法不會破壞序列的穩定性，即歸並排序也是穩定的排序演算法。

5. 由合並排序演算法談如何理解遞歸

For example ,in fellowing python :
merge(list1,list2,result):
if len(list1)==0 or len(list2) ==0: return result;
else if list1[0] <list2[0] :
return merge(list1[1:],list2,result)
else
return merge(list1,list2[1:],result)

6. C語言利用遞歸實現插入排序，選擇排序，快速排序，歸並排序演算法。 要求有注釋 ！ 謝謝各位大神！

//InsertionSort
void insertionSort(int a[], int size) {
int i, j, key;

for (i = 0; i < size; i++) {
key = a[i];
j = i-1;
while (j >= 0 && key < a[j]) { //把元素插入到之前的有序元組中
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}

//MergeSort
void merge(int a[], int p, int q, int r) { //合並兩個子元組
int i, j, k, n1, n2;
int *array1, *array2;
n1 = q - p + 1,
n2 = r - q;

array1 = (int *)calloc(n1+1, sizeof(int));
array2 = (int *)calloc(n2+1, sizeof(int));
if (array1 == NULL || array2 == NULL) {
printf("Error: calloc failed in concat\n");
exit(EXIT_FAILURE);
}
for(i = 0; i < n1; i++)
array1[i] = a[p + i];
for(i = 0; i < n2; i++)
array2[i] = a[q + 1 + i];
array1[n1] = MAXNUMBER;
array2[n2] = MAXNUMBER;
i = 0, j = 0;
for(k = p; k <= r; k++)
if(array1[i] <= array2[j])
a[k] = array1[i++];
else
a[k] = array2[j++];
free(array1);
free(array2);
}

void mergeSort(int a[], int p, int r) {//歸並的遞歸調用
int q;
if (p < r) {
q = (p+r)/2;
mergeSort(a,p,q);
mergeSort(a,q+1,r);
merge(a,p,q,r);
}
}

//QuickSort
int partition(int a[], int p, int r) {//快排的分組函數
int i, j, x, temp;
x = a[r];
i = p - 1;

for (j = p; j < r; j++)
if (x > a[j]) {
temp = a[++i];
a[i] = a[j];
a[j] = temp;
}
temp = a[++i];
a[i] = a[r];
a[r] = temp;

return i;
}

void quickSort(int a[], int p, int r) { //快排
int q;
if (p < r) {
q = partition(a, p, r);
quickSort(a, p, q-1);
quickSort(a, q+1, r);
}
}

//隨即版的quickSort
int randomPartition(int a[], int p, int r){

int i, temp;
i = rand();
while( i < p || i > r)
i = rand();
temp = a[i];
a[i] = a[r];
a[r] = temp;
return partition(a,p,r);
}

void randomQuickSort(int a[], int p, int r){
int q;
if(p < r){
q = randomPartition(a,p,r);
randomQuickSort(a,p,q-1);
randomQuickSort(a,q+1,r);
}
}
//BubbleSort();//冒泡排序
void bubbleSort(int a[], int size) {
int i, j, temp;

for (i = size -1; i >= 0; i--)
for (j = 0; j < i; j++)
if (a[j] < a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}

7. 歸並排序

先考慮一個簡單的問題：如何在線性的時間內將兩個有序隊列合並為一個有序隊列（並輸出）？

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原創
轉貼請註明出處

8. 歸並排序演算法是什麼

歸並排序演算法定義如下：

歸並排序演算法就是利用分治思想將數組分成兩個小組A，B，再將A，B小組各自分成兩個小組，依次類推，直到分出來的小組只有一個數據時，可以認為這個小組已經是有序的了，然後再合並相鄰的二個小組就可以了。這樣通過先遞歸的分解數組，再合並數組，就完成了歸並排序。

歸並排序演算法特點：

由於歸並排序在歸並過程中需要與原始記錄序列同樣數量的存儲空間存放歸並結果以及遞歸時深度為log2n(2為底)的棧空間。

因此空間復雜度為O(n+logn)，Merge函數中if(SR[i] < SR[j])語句說明需要兩兩比較，不存在跳躍，因此歸並排序是一種穩定的排序演算法，歸並排序是一種比較佔用內存，但卻效率高且穩定的演算法。

9. 請用遞歸方法寫出歸並排序的主要思想和演算法

1. 判定序列array[m，n]長度是否為1，如果為1直接返回
2. 否則分別歸並排序序列array[m, (m + n) / 2]和序列array[(m + n) / 2 + 1, n]
3. 歸並序列array[m, n]

void merge(int array[], int begin, int end)
{
if ((end - begin) <= 1)
return;
merge(array, begin, (begin + end) / 2);
merge(array, (begin + end) / 2 + 1, end);
//合並兩個數組區域。這部份就不寫了，一個序列2元素順序插入序列1的過程
}