算法导论笔记 -- Step 3 [归并排序]

**转载请注明**

接下来谈到了devide-and-conquer 方法。 （分而治之 。。。）

所以就来到了一个看起来最简单的排序。归并排序（Merge Sort):

原理：初始状态是两组已排序的数组，把他们归并到一起，方法就是每次取两个数组里最小的做比较，较小的push入结果集。

* 两摞已经排好序的牌，朝上放在桌上，每次取最小的放在手中，都取完就得到已经排好序的一摞牌了。



C++代码：

#include <iostream>

using namespace std;

//#define INT_MAX 2147483647

void MERGE_SORT ( int*, int, int );
void MERGE( int*, int, int, int );

int main(){
    int a[] = {5,2,4,6,1,3};

    MERGE_SORT(a, 0, sizeof(a)/sizeof(int)-1); //这次函数不是取长度而是最末位置了。所以－1

    for (int i = 0; i < sizeof(a)/sizeof(int); i++){
        cout << a[i] << endl;
    }
    return 0;
}

void MERGE_SORT( int* array, int start, int end ){
    int half_len = (end-start)/2;
    if ( end > start ){
        MERGE_SORT(array, start, start+half_len);
        MERGE_SORT(array, start+half_len+1, end);
    }

    MERGE(array, start, start+half_len, end);
}

void MERGE( int* array, int start, int point, int end ){
    int len1 = point - start + 1;
    int len2 = end - point;
    int tmp_arr1[len1+1];
    int tmp_arr2[len2+1];

    for ( int i = start; i <= point; i++ ){
        tmp_arr1[i-start] = array[i];
    }
    tmp_arr1[len1] = INT_MAX;

    for ( int i = point + 1; i <= end; i++ ){
        tmp_arr2[i-point-1] = array[i];
    }
    tmp_arr2[len2] = INT_MAX;

    for ( int i = start, j = 0, k = 0; i <= end; i++ ){
        if (tmp_arr1[j] <= tmp_arr2[k]){
            array[i] = tmp_arr1[j++];
        }
        else{
            array[i] = tmp_arr2[k++];
        }
    }
}

空间复杂度：
    O（n）

时间复杂度：
    O（n*lgn)