合并排序算法递归

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的过程
}