合并排序的非递归实现（自底向上设计）

桃扇骨 2022-06-09 00:17 181阅读 0赞

上一篇博文，讨论了合并排序的递归实现。这篇文章，说说合并排序的非递归实现。

# 思路描述 #

假设一个数组，共有11个（0到10）元素。  
首先，进行“1+1”合并：即第0个和第1个合并，第2个和第3个合并，……，第8个和第9个合并，第10个不用合并；  
然后，进行“2+2”合并：0~3合并，4~7合并，此时剩下3个，虽然不足4，但是大于2，所以做“2+1”合并，即8~10合并；  
再然后，进行“4+4”合并，即0~7合并，此时剩下3个，3小于等于4，所以不用合并；  
最后，进行“8+8”合并，因为总数是11，虽然不足16，但是大于8，所以做“8+3”合并.

也许上面的描述把你搞晕了，没关系，看看示意图，秒懂。

下图共11个元素，实线箭头表示合并，虚线箭头表示不做处理。

![这里写图片描述][SouthEast]

# C语言代码 #

#include <stdio.h>
    #include <string.h> //memcpy函数用这个头文件
    #include <stdlib.h> //malloc和free函数用这个头文件
    
    /* *此函数为了测试用，功能是打印数组，不想刷屏，所以没有加换行 *a是数组首地址 *len是数组长度 */
    void print_array(int *a, int len)
    {
        int i=0;
        for(i=0; i<len; ++i)
            printf("%d ",a[i]);
    }
    
    
    /* * 将两个有序数组b和c合并为一个有序数组a * b是第一个非降序数组的首地址，长度是len_b * c是第二个非降序数组的首地址，长度是len_c * a指向输出数组的首地址 * 注意：a数组需要调用者分配空间,且a数组不能与b或者c重叠 */
    
    void __merge(int *a, int *b, int len_b, int *c, int len_c)
    {
        int i = 0; // b的下标
        int j = 0; // c的下标
        int k = 0; // a的下标
        int len = len_b + len_c; //计算出a数组的长度
    
        /*循环执行条件是 i 和 j 都没有越界*/
    
        while(i < len_b && j < len_c) //&&的优先级更低 
        {
            /*比较b[i]和c[j],把较小的复制到a[k],同时i(或j)和k指向下一个元素*/
    
            if(b[i] <= c[j])
                a[k++] = b[i++];
            else
                a[k++] = c[j++];
        }
    
        if(i == len_b) //说明b已经处理完
            memcpy(a+k, c+j, (len-k)*sizeof(int));
        else         //说明c已经处理完
            memcpy(a+k, b+i, (len-k)*sizeof(int));
    }
    
    
    void __merge_two_part(int a[], int len_1, int len_2)
    {
        int *sub_1 = a;
        int *sub_2 = a + len_1;
        /* 这里可以添加调试信息，展示排序过程，比如 printf("merge "); print_array(sub_1,len_1); printf(" and "); print_array(sub_2,len_2); */
    
        int temp_len = sizeof(int) * (len_1 + len_2); //计算需要多少字节
        int *temp = malloc(temp_len); //分配临时空间
        if(temp == NULL)
        {
            printf("malloc failed\n");
            return;
        }
    
        __merge(temp,sub_1,len_1,sub_2,len_2);
    
        memcpy(a,temp,temp_len); //此时数组a已经有序
    
        /* 这里可以添加调试信息，展示排序过程，比如 printf("---> "); print_array(a,len_1 + len_2); printf("\n"); */
    
        free(temp);
    }
    
    
    void __n_and_n_merge(int a[], int a_len, int n)
    {
        int left = a_len; //left用来计数，表示还剩多少个元素没有参与合并
        int join_len = n + n;  // n并n,合并后的长度是2n,用join_len表示
    
        while(left >= join_len)
        {
            __merge_two_part(a,n,n);
            a += join_len;   //使a指向下一段
            left -= join_len;
        }
    
        /* 当不够n+n合并时，如果超过n个元素，仍然进行合并； 如果剩余元素小于等于n个，则不做处理 */      
        if(left > n) 
        {
            __merge_two_part(a,n,left-n);
        }
    }
    
    
    void merge_sort_down2up(int a[], int len)
    {
        int step = 1;        //初始步长
        while(step < len)
        {
            __n_and_n_merge(a,len,step);   //step + step 合并
            step *= 2;  
        }
    }
    
    
    
    //测试函数
    int main(void)
    {
        int a[11]={
       9,8,5,3,2,9,4,6,7,1,0};   //11个数 
    
        merge_sort_down2up(a,11);
    
        printf("最终结果：");
        print_array(a,11);
        printf("\n");
    
        return 0;
    }

# 代码讲解 #

已经在代码中添加了详细的注释，这里只说要点。  
与排序相关的函数有4个。

void __merge(int *a, int *b, int len_b, int *c, int len_c);
    void __merge_two_part(int a[], int len_1, int len_2);
    void __n_and_n_merge(int a[], int a_len, int n);
    void merge_sort_down2up(int a[], int len);

前三个属于内部函数（我以双下划线开头），第四个`merge_sort_down2up`属于开放给用户的函数，调用的时候传入整形数组名和长度即可。

`void __merge(int *a, int *b, int len_b, int *c, int len_c);`  
这个函数在上一篇博文中出现过，属于归并过程中最基本的“砖头”，此函数被第二个函数`__merge_two_part`调用。

`void __merge_two_part(int a[], int len_1, int len_2);`  
为了增强整个代码的可读性，我专门设计了这个接口。  
这个函数的目的是把一个数组的前半部分（已经为升序）和后半部分（已经为升序）进行合并排序。`int a[]`也可以写为`int *a`,用来接收数组首地址；`len_1`表示前半部分的长度，`len_2`表示后半部分的长度。  
假设数组a包含7个元素，前4个和后3个元素已经分别有序，现在要做`4+3`合并，那么应该这样用  
`__merge_two_part(a, 4, 3);`

示意图如下：

![这里写图片描述][SouthEast 1]

调用后，数组a为升序。

`void __n_and_n_merge(int a[], int a_len, int n);`  
此函数对整个数组进行`n+n`合并。  
注意：对于剩余的元素，当不够`n+n`合并时，如果大于`n`个元素，则进行`n+x`合并； 如果小于等于`n`个，则不做处理.

`a_len`表示数组长度，每次调用时保持不变，`n`表示合并的步长，取值为`1,2,4,8...`;  
`n`的初始值为`1`，反复调用此函数，调用后`n`取值翻倍，直到`n`大于等于`a_len`为止。

在`void __merge_two_part(int a[], int len_1, int len_2)`函数中添加一些打印信息，可以看出整个排序过程。截图如下：

![这里写图片描述][20170822233755970]

【参考资料】  
[http://www.cnblogs.com/xing901022/p/3671771.html][http_www.cnblogs.com_xing901022_p_3671771.html]

[SouthEast]: /images/20220609/22d8d19cb9304504bc53e86ba198d9ee.png
[SouthEast 1]: /images/20220609/99d29b574da2424490a62fd6ac1d4fae.png
[20170822233755970]: /images/20220609/40bfe415a8e84abb921e9df1ab8f645c.png
[http_www.cnblogs.com_xing901022_p_3671771.html]: http://www.cnblogs.com/xing901022/p/3671771.html