算法导论学习笔记(2)－归并排序

前还一直困惑：为什么明明归并排序比快排的时间复杂度更稳定，为什么库函数不用归并而用快排，现在知道原因了，因为归并排序必须开额外的空间，而且空间开销还比较大，下面介绍算法：

首先，归并排序用到了分治的思想，把大数据分成若干个小数据，然后再分别对小数据进行处理，最后把小数据

合并成大数据。

其次，归并排序用到了一个最重要的特点，就是把两组已经排序的数据合并成一组有序数据，并且该过程的时间复

杂度为O(n)。

最后，算法便出来了，对于一个数组A[n]来说，我们要对他进行排序，首先，我们假设A[0~n/2]和A[n/2+1,n-1]为

有序序列,那么，我们就可以在O(n)的时间内排好序，可是，问题是，A[0~n/2]和A[n/2+1,n-1]并不是有序序列，于是我们就要将他们都变成有序序列，如何变呢？我们再分别对A[0~n/2]和A[n/2+1,n-1]进行排序即可，对于A[0~n/2]来说，我们运用和以上相同的方法，把他分成A[0~n/2/2]和A[n/2+1,n/2]，然后如果这两个数组均为有序序列的话，那么就可以把它们合并起来，然后在返回到上一层了，那么如何才能判断他们为有序呢？当只有一个元素的时候这个元素便是有序的，所以，只需要递归到元素个数为1，然后再返回合并即可。

下面是对以下下代码中的merge()（合并)函数正确性的证明:

1.当第一次循环迭代的时候，i = L, A[L, i-1]为空，是有序的序列（空也算有序序列），并且含有i-L=0个LA[n1],RA[n2]的最小的数，这时c1 = c2 = 0, LA[c1]和RA[c2]均为彼此数组中的最小的元素。

2.假设第i次迭代的时候LA[c1] <= RA[c2], 这时LA[c1]便是还没有被复制到A中的最小的元素，此时A中含有i-L个最小的元素，当执行A[i] = LA[c1]时，A中便含有i-L+1个最小的元素，然后增加c1和i进行下一次迭代，如果第一次时LA[c1] > RA[c2]，执行相似的过程。

3.循环结束后，i = r+1, 此时A中含有i-L = r-L+1个最小的元素，恰好是l~r所有的元素，并且已排好序，证毕。

//insertion_sort #include <iostream> using namespace std; const int inf = (1<<28);  void print(int* A, int n) {     for (int i = 0; i < n; i++) {         cout << A[i] << " ";     }     cout << endl; } void merge(int *A, int l, int m, int r) {     int n1 = m-l+1, n2 = r-m;     int lA[(const int)(n1+1)], rA[(const int)(n2+1)];     for (int i = 0; i < n1; i++) {         lA[i] = A[i+l];     }     for (int i = 0; i < n2; i++) {         rA[i] = A[m+1+i];     }     lA[n1] = rA[n2] = inf;     int c1 = 0, c2 = 0;     for (int i = l; i <= r; i++)     {         if (lA[c1] <= rA[c2]) {             A[i] = lA[c1++];         }         else {             A[i] = rA[c2++];         }     } } void merge_sort(int *A, int l, int r) {     if (l < r)     {         int m = (l + r) / 2;         merge_sort(A, l, m);         merge_sort(A, m+1, r);         merge(A, l, m, r);     } } int main() {     int A[10] = {43,2,53,1,8,29,52,4,8,10};          cout << "before sorted: ";     print(A, 10);          merge_sort(A, 0, 10);          cout << "after sorted: ";     print(A, 10);          return 0; }