手写归并排序算法
【摘要】 归并排序算法,是基于分而治之的思想,核心思路为:要对一个数组进行归并排序,则先把这个数组从中间切开,变成2个子数组。然后对每个子数组进行归并排序,最后,2个排好序的子数组再合并成一个有序的数组,这样整个数组的排序就完成了。而对每个子数组进行归并排序,又使用了上述的算法过程,因此是个递归调用。当子数组只有一个元素时,归并排序函数直接返回。因此,归并排序算法的过程,包括:二分法,切分成2个子数组...
归并排序算法,是基于分而治之的思想,核心思路为:
要对一个数组进行归并排序,则先把这个数组从中间切开,变成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++;
}
}
}
我的微信号是 实力程序员,欢迎大家转发至朋友圈,分享给更多的朋友。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)