写点什么

手写归并排序算法

发布于: 3 小时前

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


要对一个数组进行归并排序,则先把这个数组从中间切开,变成 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++;        }    }}
复制代码


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

发布于: 3 小时前阅读数: 3
用户头像

实力程序员,用实力说话! 2021.05.24 加入

超过20年一线产品研发和技术管理的实力程序员

评论

发布
暂无评论
手写归并排序算法