归并排序

归并排序MergeSort

<a name = "1">思路</a>

思路:
如对一个数组A排序，将A分为（B C）再分B C-(E F G H) 直到分为的小数组含有两个元素对其排序，再依次往上层有序归并。

效率归并排序所需要的时间和NlgN成正比，在小规模数组处理上(比如分到15个元素的数组了)可以考虑使用插入排序，递归是小规模的比较上过于频繁，所以可以提高效率。

说明:

划分数组

然后对a , b, c, d进行一个算法就可以了。

<a name = "1">原地归并算法</a>

对a, b 数组进行运算合成 e<3 4 5 9>
对c, d 数组进行运算合成 f<1 2 7 8>
对e, f 数组进行运算合成 g<1 2 3 4 5 7 8 9>

这里的运算都有同一个功能就是把两个有序的数组合成一个有序的数组，这个运算就是原地归并算法, 这个算法很简单。

那原地归并算法是怎样实现对两个有序的数组合成一个有序的数组呢?这个很好解决。两个数组都从自己开头判断, 小的元素保存到一个备份结果数组中, 这个元素肯定是最小值，然后在在省下的用同样方式找出最小值保存, 依次类推。具体代码如下:

void merge(int *data, int head, int mid, int rear){
    int copydata[N];
    int i = head, j = mid + 1;
    
    for (int k = head; k < N; k++) {
        copydata[k] = data[k];
    }
    
    for (int k = head; k <= rear; k++) {
        if (i > mid) {
            data[k] = copydata[j++];
        } else if (j > rear) {
            data[k] = copydata[i++];
        } else if(copydata[j] < copydata[i]) {
            data[k] = copydata[j++];
        } else {
            data[k] = copydata[i++];
        }
    }
    
}

合成有序数组问题解决之后下一个问题就是划分了, 这里有递归(recursive)划分和非递归两种方式。我先介绍非递归方式。

<a name = "1">顶向下非递归归并排序</a>

比如对数组a({4, 5, 1, 2});进行归并排序需要进行:

merge(a, 0, 1, 2) 即 4 5
merge(a, 2, 3, 3) 即 1 2
merge(a, 0, 2, 3) 整体

我们可以按规律写一个循环
code

void mergesort_nonrecursive(int *data, int size){
    int subsize, i;
    int head, mid, rear;
    for(subsize = 2;subsize < size*2;subsize *= 2){
        
        
        for(i = 0;i < size;i += subsize){
            head = i;
            mid = head + subsize/2;
            rear = head + subsize;
            if(rear >= size - 1) rear = size - 1;
            merge(data, head, mid, rear);
        }
        
    }   
}

但是能不能按照其他写法依然实现3次merge，以下是递归写法，

<a name = "1">顶向下递归归并排序</a>

算法很好理解，但是这几行代码不怎么好理解。不知道作者怎么写出来的, 感觉很神奇。如果您有什么更好的理解，可以留言。

任然实现了这3个函数

merge(a, 0, 1, 2) 即 4 5
merge(a, 2, 3, 3) 即 1 2
merge(a, 0, 2, 3) 整体
值得提醒的是递归是函数压栈的过程，执行完会跳回调用处，往后继续执行，所以还是有保量保存着之前的值。
执行顺序如下图：

执行顺序图

<a name = "1">低向上归并排序</a>

这个就很好理解了，全部 2， 2 归并，然后 4， 4 逐步往复。

自底向上归并

     int auk[N];
    for (int i = 0; i < N; i++) {
        auk[i] = data[i];
    }
    
    for (int sz = 1; sz < N; sz *= 2) {
        
        for (int lo = 0; lo < N - sz; lo += (sz + sz)) {
            
            printf("%d %d %d\n", lo, lo + sz - 1, lo + sz + sz - 1 > N - 1?N-1:lo + sz + sz -1);
            
            merge(data, lo, lo + sz - 1, (lo + sz + sz - 1 > N - 1?N-1:lo + sz + sz -1));
        }
    }