详解八大排序（四）------（归并排序）
文章目录
- 前言：
- 1 递归版本（MergeSort）
- 1.1 核心思路
- 1.2 实现代码
- 2 非递归版本（MergeSortNonR）
- 2.1 核心思路
- 2.2 实现代码
- 3.完整代码
前言：
归并排序的核心思路是把数组里面的数两两分成一组，组内比较完大小之后，再把组外的融合进组内进行比较。
以下两个版本的核心思路也是这样。只是分组的方法不同。
1 递归版本（MergeSort）
1.1 核心思路
递归版本利用递归的思路，来实现对数组的分组。
以上述待排序数组为例。将第一个数定义为left，最后一个数定义为right，再将（left + right）/ 2定义为mid。
以mid为中心，把数组分为[left,mid][mid + 1,right]两个数组。得到：
重复上面的步骤，再次二分。得到：
将数组分成剩下2个数时，开始比较。从第一个数组开始比较，也就是[6,1]。比较完成后，再将[2,7]与第一个数组融合，再次进行比较。得到：
重复上面的步骤，将第一个数组的内容比较完成，再将第二个数组与第一个数组融合。得到：
继续重复上面的步骤，直到数组排序完成。得到：
1.2 实现代码
// 归并排序递归实现
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right)//递归终止的信号---当数组里只剩下一个数时，就应该返回递归
{
return;
}
int mid = (left + right) / 2;//定义mid
_MergeSort(arr, left, mid, tmp);//数组二分之后，先从左边接着二分
_MergeSort(arr, mid + 1, right, tmp);//左边二分完成后，再看数组的右边
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;//运用双指针的思维，来对数组进行排序
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else {
tmp[index++] = arr[begin2++];
}
}
//循环退出，说明begin1和begin2有一个大于end2
//另一个没有比较完
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//收尾工作，确保两个组都能比较完
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
//把比较好的数放回原数组。本来上述程序比较好的数本来放在tmp这个临时数组
}
//核心思路是把数组分成两个数一组，一组一组比较，比较完再把下一个组融合进来比较
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}
2 非递归版本（MergeSortNonR）
2.1 核心思路
非递归版本的核心思路就是利用区间的思维，来对数组进行区间的划分。
以上述数组为例。已知数组的大小为7。那么可以将区间的划分次数定义为n / 3 + 1。也就是3次。定义一个gap = 1。每次比较完，gap都会 *= 2。直到gap > n。再定义一个i，i是确保能把数组的比较数量。得到：
i是数组比较的区间。我们第一次比较是在区间[0,2)，比较完成后，再比较区间[2,4)，再比较[4,6)。直到数组里所有成员两两比较完之后。得到：
此时进入下一个gap，也就是gap = 2。重新开始比较。得到：
此时，再次比较数组里的成员。得到：
这里比较完成，再把数组合在一起进行比较。得到：
剩下的就是对整个数组进行比较。得到最终排序好的数组：
2.2 实现代码
// 归并排序非递归实现
void MergeSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
for (int gap = 1; gap < n; gap *= 2)//将数组的区间划分成gap组
{
int index = 0;
for (int i = 0; i < n; i += 2 * gap)//确保比较的成员是从两两开始的
{
int begin1 = i, end1 = i + gap;
int begin2 = i + gap, end2 = i + 2 * gap;
if (end1 > n)
break;
if (end2 > n)
end2 = n;
//end1 和 end2 的定义存在越界的风险，所以在开始比较之前，确认end1 和 end2 没有越界
//双指针法进行比较并记录在tmp中
while (begin1 < end1 && begin2 < end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
//循环结束，说明此时begin1和begin2有一个等于end
//确保begin1和begin2能比较完所有的数
while (begin1 < end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 < end2)
{
tmp[index++] = arr[begin2++];
}
//将比较好的数从tmp中移植到原数组arr
for (int j = i; j < end2; j++)
{
arr[j] = tmp[j];
}
}
}
free(tmp);
tmp = NULL;
}
3.完整代码
#include<stdio.h>
#include<stdlib.h>
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//打印函数
void PrintArr(int* arr,int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// 归并排序递归实现
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right)//递归终止的信号---当数组里只剩下一个数时，就应该返回递归
{
return;
}
int mid = (left + right) / 2;//定义mid
_MergeSort(arr, left, mid, tmp);//数组二分之后，先从左边接着二分
_MergeSort(arr, mid + 1, right, tmp);//左边二分完成后，再看数组的右边
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;//运用双指针的思维，来对数组进行排序
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else {
tmp[index++] = arr[begin2++];
}
}
//循环退出，说明begin1和begin2有一个大于end2
//另一个没有比较完
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//收尾工作，确保两个组都能比较完
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
//把比较好的数放回原数组。本来上述程序比较好的数本来放在tmp这个临时数组
}
//核心思路是把数组分成两个数一组，一组一组比较，比较完再把下一个组融合进来比较
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}
// 归并排序非递归实现
void MergeSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
for (int gap = 1; gap < n; gap *= 2)//将数组的区间划分成gap组
{
int index = 0;
for (int i = 0; i < n; i += 2 * gap)//确保比较的成员是从两两开始的
{
int begin1 = i, end1 = i + gap;
int begin2 = i + gap, end2 = i + 2 * gap;
if (end1 > n)
break;
if (end2 > n)
end2 = n;
//end1 和 end2 的定义存在越界的风险，所以在开始比较之前，确认end1 和 end2 没有越界
//双指针法进行比较并记录在tmp中
while (begin1 < end1 && begin2 < end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
//循环结束，说明此时begin1和begin2有一个等于end
//确保begin1和begin2能比较完所有的数
while (begin1 < end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 < end2)
{
tmp[index++] = arr[begin2++];
}
//将比较好的数从tmp中移植到原数组arr
for (int j = i; j < end2; j++)
{
arr[j] = tmp[j];
}
}
}
free(tmp);
tmp = NULL;
}
int main()
{
//int arr[] = { 5,2,7,8,1,3,9,4,6 };
int arr[] = { 4,2,1,8,5,6,9,5 };
//int arr[] = { 2,3,6,5 };
int sz = sizeof(arr) / sizeof(int);
printf("排序前：");
PrintArr(arr, sz);
//MergeSort(arr, sz);
MergeSortNonR(arr, sz);
printf("排序后：");
PrintArr(arr, sz);
return 0;
}