剑指offer之归并排序 2

5 总结

归并排序，我们需要对数组里面的几个子数组元素进行对比然后移动下标操作，感觉非常复杂，这个时候我们应该借助辅助数组来实现，不就是对比2个数组里面的数据吗？我们把辅助数组的大小设置2个数组元素大小之和，然后搞2个首指针，对比，然后哪个数据小，就插入到辅助数组，然后移动相应的指针就行，然后有一个数组里面的数据肯定都会插入到辅助数组，我们再把另外一个数组里面剩余的元素插入辅助数组，辅助数组就排序好了，然后我们再把辅助数组辅助给原数组就ok了。

1 、4 和 2 、3

辅助数组里面的值变化

1    *      *      *
 
1    2     *      *
 
1    2     3     *
 
1    2     3     4      

归并排序用到了辅助数组和2首指针思想，等辅助数组排序好了再赋值给原数组，打死也不要忘记。

这个问题的本质我们需要知道两个排序的数组，如果能移动里面的数据，确保两个数组的数据依次是都是排序的，比如我们数组如下

int source[] = {2, 6, 1, 4, 5, 9, 3, 7, 8};

现在我们把这个数组里面的部分原始分割成2部分，列如第一个元素2和第二个元素6是一个子数组，第三个元素1和第四个元素4是一个子数组，每个子数组排序都好了，我们现在需要把这个2个子数组里面的数据进行排序，也就是2个子数组的起始下标是0~1  2~3排序好了后把原数组变成

1 2 4 6 5 9 3 7 8

我们实现标准的通用代码如下

#include <stdio.h>
 
void printDatas(int* datas, int len)
{
    for (int i = 0; i < len; ++i)
    {
        printf("%d\t", datas[i]);
    }
    printf("\n");
}
 
void sort(int* datas, int start1, int end1, int start2, int end2)
{
    if (datas == NULL)
    {
        printf("datas is NULL\n");
        return;
    }
    if (start1 > end1 || start2 > end2)
    {
        printf("start1 > end1 || start2 > end2\n");
        return;
    }
    int length = end1 - start1 + end2 - start2 + 2;
    int copy[length];
    int i = start1, j = end1, k = start2, h = end2, m = 0, n = 0;
    //用2个指针把指向的值进行对比，然后向右移动，这里需要要求2个数组都是排序好的，
    while (i != j + 1 && k != h + 1)
    {
        if (datas[i] > datas[k])
        {
            copy[m++] = datas[k++];
        }
        else 
        {
            copy[m++] = datas[i++];
        }
    }
    //把剩余的一个数组里面的值赋值给我们的copy数组
    while (i != j + 1)
         copy[m++] = datas[i++];
    while (k != h + 1)
         copy[m++] = datas[k++];   
     //把copy数组再赋值给原数组
    printDatas(copy, length);
    i = start1;
    k = start2;
    for (; n <= end1 - start1; ++n)
    {
         datas[i++] = copy[n];
    }
    for (; n < length; ++n)
    {
        datas[k++] = copy[n];
    }
}
 
int main(void) { 
    int source[] = {2, 6, 1, 4, 5, 9, 3, 7, 8};
    int length =  sizeof(source) / sizeof(int) ;
    printDatas(source, length);
    int temp[9];
    sort(source, 0, 1, 2, 3);
    printDatas(source, length);
    return 0;
}
 
       

运行结果如下

现在如果我的2个子数组的起始下标不是0~1和2~3，是0~1和6~8，我们把上面的函数

sort(source, 0, 1, 6, 8);

我们再看运行结果

2 3 1 4 5 9 6 7 8

注意我们这这个sort函数（void sort(int* datas, int start1, int end1, int start2, int end2)），不满足两个子数组数据有交叉的情况，但是对于两个数组的长度没有限制（在合法情况），而且这个两个数组可以不连续， 原始的5个数组是1 2 3 7 8 现在变成了2 3 6 7 8，说明没毛病

然后我们归并排序里面，只不过我们的end1就是mid值，然后start2的值是mid + 1的值，两个子数组是连续的，然后长度也是一致，属于上面的特殊情况。

归并排序是稳定排序算法，适合子数组序列排好序。