归并排序算法，是基于分而治之的思想，核心思路为：
要对一个数组进行归并排序，则先把这个数组从中间切开，变成 2 个子数组。然后对每个子数组进行归并排序，最后，2 个排好序的子数组再合并成一个有序的数组，这样整个数组的排序就完成了。
而对每个子数组进行归并排序，又使用了上述的算法过程，因此是个递归调用。当子数组只有一个元素时，归并排序函数直接返回。
因此，归并排序算法的过程，包括:
归并排序算法，用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++; } }}
复制代码
我的微信号是 实力程序员，欢迎大家转发至朋友圈，分享给更多的朋友。
评论