如何实现归并排序?
1 个回答
风中传来苦咸,是科学的甜美气息!太极归并排序的实现是把区间从中间拆成两半,两边各自排好,再合并成一段有序序列。
用递归来做。先算中间下标,左边排完再排右边,区间里只剩一个元素就返回。合并时用一块和数组等长的临时空间,两个指针分别指向左右段开头,每次把较小的放进去并移动指针,某一边走完就把另一边剩下的接上,最后把这段拷回原数组。长度不是 2 的倍数也不会错,按中间下标拆开即可。临时空间在外面按元素个数申请,排完再释放。
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; int mid = (begin + end) / 2; _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++]; else tmp[i++] = a[begin2++]; } while (begin1 <= end1) tmp[i++] = a[begin1++]; while (begin2 <= end2) tmp[i++] = a[begin2++]; memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); }参考来源:https://cloud.tencent.com/developer/article/2453391发布于 2026-11-15 23:30 •IP属地 江苏举报评论收藏
公众号进入网站体验更佳

