归并排序

一：思想

归并排序是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

二：实现步骤

假设对这个数组进行归并排序：

第一步：分解

第二步：合并

解释：

1：需要注意的是合并是在辅助数组tmp上进行的，而不是直接在原数组 a 上进行操作，因为这可能会导致a数组的数据被覆盖

2：其次是10 6 合并在tmp数组上为 6 10，然后tmp数组就把6 10 复制给 a数组，即边排序，排序好了就还给a数组，再去下一次排序，

总：

三：代码

1：递归实现归并排序

void _MergeSort(int* a, int* tmp, int begin, int end)
{// 递归终止条件：如果开始索引大于或等于结束索引，说明子数组长度为0或1，无需排序，直接返回if (begin >= end)return;// 计算中间索引midint mid = (begin + end) / 2;// 递归排序左半部分_MergeSort(a, tmp, begin, mid);// 递归排序右半部分_MergeSort(a, tmp, mid + 1, end);// 以下是合并两个已排序的子数组的逻辑// 初始化左右子数组的起始和结束索引int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;// 初始化辅助数组tmp的索引int index = begin;// 合并两个子数组，直到其中一个子数组全部合并完while (begin1 <= end1 && begin2 <= end2){// 如果左子数组的当前元素小于右子数组的当前元素，则将左子树的当前元素复制到辅助数组中if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}// 否则，将右子数组的当前元素复制到辅助数组tmp中else{tmp[index++] = a[begin2++];}}// 如果左子数组还有剩余元素，将其全部复制到辅助数组中while (begin1 <= end1){tmp[index++] = a[begin1++];}// 如果右子数组还有剩余元素，将其全部复制到辅助数组中while (begin2 <= end2){tmp[index++] = a[begin2++];}// 将辅助数组tmp中已排序的元素复制回原数组memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//开辟tmp数组
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc failed");exit(-1);}_MergeSort(a, tmp, 0, n - 1);//忘记freefree(tmp);
}

a：解释memcpy：

1：

在归并排序的实现中，使用了一个辅助数组 tmp 来存储合并过程中排序好的元素。这是因为归并排序的合并步骤需要将两个已排序的子数组合并成一个新的已排序的数组，而不希望直接在原数组 a 上进行操作，因为这可能会导致数据覆盖。

在合并子数组的步骤完成后，tmp 数组中的从索引 begin 到 end 的部分包含了已经正确排序的元素。此时，需要将这些元素复制回原数组 a 的相应位置，以便原数组 a 也保持正确的排序顺序。

2：

a + begin 是指向原数组 a 中要开始复制位置的指针。由于 a 是一个整数数组，a + begin 实际上是指向 a[begin] 的指针。

tmp + begin 是指向辅助数组 tmp 中要开始复制的数据源的指针。同样，它指向 tmp[begin]。
(end - begin + 1) * sizeof(int) 计算要复制的字节数。这里 (end - begin + 1) 计算了从 begin 到 end 的元素个数（包括 begin 和 end），sizeof(int) 获取一个整数元素的大小，将这两个值相乘就得到了要复制的总字节数。

因此，这行代码的作用是将辅助数组 tmp 中从索引 begin 到 end 的已排序元素复制到原数组 a 的相应位置，确保 a 中的这部分元素现在是有序的。通过这种方式，归并排序的合并步骤能够正确地更新原数组，使其最终完全有序。

b：解释（ int index = begin）：

index控制的是tmp 的下标，但是不是从0开始，而是从begin开始，因为如果归并的是a数组中的第三个和第四个元素，那排好序后应该放在tmp的第三个和第四个位置上，这叫位置的一一对应，可以有效的避免错误。

2：非递归实现归并排序

void MergeSortNoneR(int* a, int n)
{// 动态分配一个与原数组a大小相同的辅助数组tmpint* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){// 如果内存分配失败，输出错误信息并退出程序perror("malloc failed");exit(-1);}// gap 表示当前每次需要合并的子数组的长度int gap = 1;while (gap < n){// 遍历数组，每次合并长度为 gap 的相邻子数组for (int i = 0; i < n; i += 2 * gap){// 初始化子数组的起始和结束索引int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;// 初始化辅助数组的索引int index = i;// 如果第二个子数组的起始索引超出数组范围，跳出循环if (begin2 >= n){break;}// 如果第二个子数组的结束索引超出数组范围，调整结束索引if (end2 >= n){end2 = n - 1;}// 合并两个子数组while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}// 如果第一个子数组还有剩余元素，将其复制到辅助数组while (begin1 <= end1){tmp[index++] = a[begin1++];}// 如果第二个子数组还有剩余元素，将其复制到辅助数组while (begin2 <= end2){tmp[index++] = a[begin2++];}// 将辅助数组tmp中已排序的元素复制回原数组amemcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}// 每次合并完成后，子数组的长度翻倍gap *= 2;}// 释放辅助数组的内存free(tmp);
}

a：解释两个数组的begin和end 的定义

int begin1 = i;

begin1 是第一个子数组的起始索引。在每次 for 循环迭代中，i 表示当前合并操作的起始位置。因此，begin1 被设置为 i，表示第一个子数组的第一个元素的位置。

int end1 = i + gap - 1;

end1 是第一个子数组的结束索引。由于每个子数组的长度是 gap，所以第一个子数组的最后一个元素的索引是 i + gap - 1。如果 gap 是子数组的长度，那么 end1 就是第一个子数组的最后一个元素。

int begin2 = i + gap;

begin2 是第二个子数组的起始索引。第二个子数组紧跟在第一个子数组之后，因此它的起始索引是第一个子数组的结束索引加 1，即 i + gap。

int end2 = i + 2 * gap - 1;

end2 是第二个子数组的结束索引。第二个子数组的长度同样是 gap，所以它的最后一个元素的索引是 i + 2 * gap - 1。然而，需要注意的是，如果 i + 2 * gap - 1 超出了数组的总长度 n，那么 end2 将在后续的代码中被调整为 n - 1，以避免数组越界。

这些索引变量 begin1, end1, begin2, 和 end2 一起定义了两个相邻的子数组，这两个子数组将在tmp中被合并成一个有序的子数组，并最终复制回原数组 a 中。通过这种方式，非递归归并排序逐步将整个数组排序。

b：解释越界问题

begin1肯定不会越界因为他是=i，永远<n

①：end1有可能越界其越界 begin1和end2就一定越界
这种情况不用归并了，因为第二个数组已经不存在，而且第一个数组虽然不完整但是有序

②：end1没越界，begin2越界，其越界，end2一定越界
这种情况也不用归并，因为第二个数组已经不存在，而且第一个数组都是完整且有序的

③：只有end2越界
需要归并，因为第一个和第二个数组都存在，所以要正确修改end2下标，end2 = n-1，然后继续和前面数组的归并即可

①②两点都是第二点，因为两种都有begin2一定越界，所以只用②即可

c：解释int gap = i

与递归实现的归并排序是一样的：

index控制的是tmp 的下标，但是不是从0开始，而是从i开始，因为如果归并的是a数组中的第三个和第四个元素，那排好序后应该放在tmp的第三个和第四个位置上，这叫位置的一一对应，可以有效的避免错误。

d：解释memcpy

在非递归归并排序的实现中，一旦两个子数组被合并成有序的子数组并存储在辅助数组 tmp 中，就需要将这些已排序的元素复制回原数组 a 中。这行 memcpy 代码就是执行这个操作的：

复制

memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));

下面是对这行代码的详细解释：

a + i 是指向原数组 a 中开始复制位置的指针。
tmp + i 是指向辅助数组 tmp 中开始复制的数据源的指针。
(end2 - i + 1) 计算要复制的元素数量。end2 是第二个子数组的结束索引，而 i 是这两个子数组的起始索引。(end2 - i + 1) 表示从索引 i 到 end2 的元素总数，包括这两个索引上的元素。

注意：

a：不能end2-begin1，因为begin1在归并过程中会被改变（下面的begin++）

b：不能（i + 2 * gap - 1 ） - i +1 ，因为i + 2 * gap - 1可以会越界，end2不会，因为在下面的越界判断中，end2即使越界了，也被修正正确了

因此，这行代码的作用是将辅助数组 tmp 中从索引 i 到 end2 的已排序元素复制到原数组 a 的相应位置。通过这种方式，原数组 a 中从索引 i 开始的 end2 - i + 1 个元素现在是有序的，这完成了归并排序的一个合并步骤。

四：程序运行效果

千万数据：

解释：千万数据，二者都花了不到一秒。

五：代码分享

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
// 时间复杂度O(N*logN)  空间复杂度:O(N)
//递归 归并排序
void _MergeSort(int* a, int* tmp, int begin, int end)
{// 递归终止条件：如果开始索引大于或等于结束索引，说明子数组长度为0或1，无需排序，直接返回if (begin >= end)return;// 计算中间索引midint mid = (begin + end) / 2;// 递归排序左半部分_MergeSort(a, tmp, begin, mid);// 递归排序右半部分_MergeSort(a, tmp, mid + 1, end);// 以下是合并两个已排序的子数组的逻辑// 初始化左右子数组的起始和结束索引int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;// 初始化辅助数组tmp的索引int index = begin;// 合并两个子数组，直到其中一个子数组全部合并完while (begin1 <= end1 && begin2 <= end2){// 如果左子数组的当前元素小于右子数组的当前元素，则将左子树的当前元素复制到辅助数组中if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}// 否则，将右子数组的当前元素复制到辅助数组tmp中else{tmp[index++] = a[begin2++];}}// 如果左子数组还有剩余元素，将其全部复制到辅助数组中while (begin1 <= end1){tmp[index++] = a[begin1++];}// 如果右子数组还有剩余元素，将其全部复制到辅助数组中while (begin2 <= end2){tmp[index++] = a[begin2++];}// 将辅助数组tmp中已排序的元素复制回原数组memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc failed");exit(-1);}_MergeSort(a, tmp, 0, n - 1);//忘记freefree(tmp);
}
//非递归 归并 排序
void MergeSortNoneR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc failed");exit(-1);}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;int index = i;if (begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}//memcpy(a + i, tmp + 1, (2 * gap) * sizeof(int));// （i + 2 * gap - 1 ） - i  +1 是错的，因为end2 在下面有可能被修改memcpy(a + i, tmp + 1, (end2 - i + 1) * sizeof(int));}gap *= 2;}free(tmp);}
void TestOP()
{srand(time(0));const int N = 10000000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; i++){a1[i] = rand() + i;a2[i] = a1[i];}int begin1 = clock();MergeSort(a1, N);int end1 = clock();int begin2 = clock();MergeSortNoneR(a2, N);int end2 = clock();//PrintArray(a1, N);printf("MergeSort:%d \n", end1 - begin1);printf("MergeSortNoneR:%d \n", end2 - begin2);free(a1);free(a2);
}
int main()
{TestOP();return 0;
}