手写归并排序算法

本文详细介绍了归并排序的分而治之思想,通过递归将数组拆分为子数组并逐一排序,最终合并为有序数组。C语言实现的归并排序代码展示了如何合并相邻有序子数组,并探讨了改进方法,避免额外内存分配。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

归并排序算法,是基于分而治之的思想,核心思路为:


要对一个数组进行归并排序,则先把这个数组从中间切开,变成2个子数组。然后对每个子数组进行归并排序,最后,2个排好序的子数组再合并成一个有序的数组,这样整个数组的排序就完成了。


而对每个子数组进行归并排序,又使用了上述的算法过程,因此是个递归调用。当子数组只有一个元素时,归并排序函数直接返回。

因此,归并排序算法的过程,包括:

  • 二分法,切分成2个子数组;
  • 递归对2个子数组进行归并排序;
  • 将2个排好序的子数组,合并为1个有序数组。


归并排序算法,用​C语言实现,代码如下:

void merge_sort(int* parr, int left, int right) {  // both left and right are inclusive
    if (left >= right) return;

    int mid = (left + right) / 2;
    merge_sort(parr, left, mid);
    merge_sort(parr, mid + 1, right);
    merge_sub_array(parr, left, mid, right);
}


两个相邻的有序子数组,合并为一个有序数组的实现代码为:

static void merge_sub_array(int* parr, int left, int mid, int right) {
    int cnt = right - left + 1;
    int* pnew = (int*)malloc(cnt * sizeof(int));
    int nidx = 0;

    int lidx = left, ridx = mid + 1;
    while ((lidx <= mid) && (ridx <= right)) {
        pnew[nidx++] = (parr[lidx] <= parr[ridx]) ? parr[lidx++] : parr[ridx++];
    }

    while (lidx <= mid) {
        pnew[nidx++] = parr[lidx++];
    }

    while (ridx <= right) {
        pnew[nidx++] = parr[ridx++];
    }

    memcpy(parr + left, pnew, cnt*sizeof(int));
    free(pnew);
}

上述代码中,使用了malloc分配一块新的内存,用于存储合并后的数据,然后再复制回原数组中,最后free掉这块内存。


其实,我们可以再改进一下,不分配额外的内存,就在原数组的内存位置上,将两个相邻的有序子数组进行合并,代码如下:

static void merge_sub_array(int* parr, int left, int mid, int right) {
    int lidx = left, ridx = mid + 1;
    while ((lidx <= mid) && (ridx <= right)) {
        if (parr[lidx] <= parr[ridx]) {
            lidx++;
        } else {
            int val = parr[ridx];
            memmove(parr + lidx + 1, parr + lidx, (ridx - lidx) * sizeof(int));
            parr[lidx++] = val;
            mid++;
            ridx++;
        }
    }
}


​我的微信号是 实力程序员,欢迎大家转发至朋友圈,分享给更多的朋友。

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值