归并排序
递归写法
思路:
如果给出两个有序数组，我们很容易可以将它们合并为一个有序数组。因此当给出一个无序数组时，我们先将它们均分为两组有序数组，在将这两组有序数组合并为一个有序数组；而将原数组分成2组 有序数组的思路又是归并排序。
递归的结束条件是什么?
当递归区间只有一个元素时结束递归
使用归并排序排
3 5 7 6 9 2 10 8详细过程如下:
代码
void _MergeSort(int* arr, int* tmp, int begin, int end)
{
//递归终止条件--区间只有一个数
if (begin == end)
return;
//将数据均分未2组
int mid = (begin + end) >> 1;
int i = begin;
//使两组均有序
_MergeSort(arr, tmp, begin, mid);
_MergeSort(arr, tmp, mid + 1, end);
//有序数组归并---归并到tmp数组中
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[i++] = arr[begin1++];
else
tmp[i++] = arr[begin2++];
}
while (begin1 <= end1) tmp[i++] = arr[begin1++];
while (begin2 <= end2) tmp[i++] = arr[begin2++];
//数据拷贝回元素组中
memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//归并排序
//时间复杂度O(nlogn)
//空间复杂度O(n+logn)
void MergeSort(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);//tmp作为临时数组存放有序数组合并后的数据
_MergeSort(arr, tmp, 0, sz - 1); //因为要借助临时数组所以构造子函数
free(tmp);
}
注意:
由于
mid是向上取整，所以不存在递归区间不存在的情况，结束条件只有区间只有一个值每次拷贝时是从
arr+begin处开始拷贝
非递归写法
归并排序的非递归写法不能和快速排序一样通过栈实现，如果使用栈存归并的区间，那么每次取出区间归并时栈顶元素出栈。这就导致了栈中不在存放有关该区间的任何信息，但是归并排序要求对区间的值进行保存，所以不能使用栈来实现
思路:
对数组依次进行一一归并、两两归并、四四归并，直至数组最终有序。
代码
//归并排序非递归
void MergeSortNonR(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);//临时数组用来存放分组排序的结果
assert(tmp);
int gap = 1;//从间隔为1开始归并
while (gap < sz)
{
int j = 0;
for (int i = 0; i < sz; i += 2 * gap)//以gap为间隔归并完一组后归并下一组
{
//有序数组归并---归并到tmp数组中
int begin1 = i, end1 = begin1 + gap - 1;
int begin2 = end1 + 1, end2 = begin2 + gap - 1;
//归并区间
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
while (begin1 <= end1) tmp[j++] = arr[begin1++];
while (begin2 <= end2) tmp[j++] = arr[begin2++];
}
//拷贝回元素组中
memcpy(arr, tmp, sizeof(int) * sz);
gap *= 2;
}
运行结果
看似没有问题，但是当我们在原数组基础上添加1个数据再排序时程序会崩溃
我们走读代码看看哪里出了问题
当
gap=2，i = 8时，begin1 = 8, end1 = 9，此时在访问arr[end1]就会越界。同理，如果数组元素是10个，那么当gap=4,i = 8时，begin1 = 8, end1 = 11,此时访问arr[end1]同样会越界，所以只有当数组元素为2的幂次方时，上述排序才正确。因此我们需要对上述代码进行修改
修改:数组越界一共有3种情况，分别是end1越界,begin1越界,end2越界
修正方案1.归并一段拷贝一段
上面已经提过了当数据个数为9个时，两两归并时会访问arr[9], 并且将该值拷贝到不属于我们创建的堆空间中。造成了越界访问
为了避免将原数组外的空间拷贝我们选择归并一段拷贝一段，只拷贝我们当趟已经归并的区间.
如果end1或者begin2越界，直接break不归并这段区间也就拷贝，剩余的数据交给gap增大的下一次归并；如果遇见end2越界，则修正end2为sz-1,归并区间[begin1,end1]和[begin2, end2]
代码
//归并排序非递归(归并一趟拷贝一趟)
void MergeSortNonR(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);//临时数组用来存放分组排序的结果
assert(tmp);
int gap = 1;//从间隔为1开始归并
while (gap < sz)
{
int j = 0;
for (int i = 0; i < sz; i += 2 * gap)
{
//有序数组归并---归并到tmp数组中
int begin1 = i, end1 = begin1 + gap - 1;
int begin2 = end1 + 1, end2 = begin2 + gap - 1;
//end1越界或者begin2越界跳出剩下为归并的数据交给下一次处理
if (end1 >= sz || begin2 >= sz)
{
break;
}
//end2越界,修正end2
if (begin2 < sz && end2 >= sz)
{
end2 = sz - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
while (begin1 <= end1) tmp[j++] = arr[begin1++];
while (begin2 <= end2) tmp[j++] = arr[begin2++];
//归并一段拷贝一段
memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
//拷贝回元素组中
//memcpy(arr, tmp, sizeof(int) * sz);
gap *= 2;
}
修正方案2.修正区间
方案1是归并一段拷贝一段，越界的那一部分区间不进行处理，让下一趟归并处理上一趟违为归并的数据。
方案2是先将越界的那一部分区间进行修正(修正的区间可能合法也可能不合法)，在对区间进行以gap为间隔的归并，每次归并完整个数组后再拷贝(方案1归并完一个区间就拷贝)。
代码
//归并排序非递归(修正区间)
void MergeSortNonR(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);//临时数组用来存放分组排序的结果
assert(tmp);
int gap = 1;//从间隔为1开始归并
while (gap < sz)
{
int j = 0;
for (int i = 0; i < sz; i += 2 * gap)
{
//有序数组归并---归并到tmp数组中
int begin1 = i, end1 = begin1 + gap - 1;
int begin2 = end1 + 1, end2 = begin2 + gap - 1;
//end1越界
if (end1 >= sz)
{
//end1修正为边界
end1 = sz - 1;
//[begin2, end2]修正为不存在的区间
begin2 = sz;
end2 = sz - 1;
}
else if (begin2 >= sz)
{
//修正为不存在的区间
begin2 = sz;
end2 = sz - 1;
}
else if (end2 >= sz)
{
end2 = sz - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
while (begin1 <= end1) tmp[j++] = arr[begin1++];
while (begin2 <= end2) tmp[j++] = arr[begin2++];
}
//拷贝回元素组中
memcpy(arr, tmp, sizeof(int) * sz);
gap *= 2;
}
free(tmp);
}
算法优化
假设我们排100000个数据，归并排序每次排序都会进行递归调用，每一个区间都会递归调用2次，因此当递归区间长度减小到某一个数时，该递归区间在进行递归调用时递归的次数就会非常多
总共递归 2 h − 1 次，最后一层递归次数占了全部的 % 50 , 倒数第二层的递归调用占了全部的 % 25 , , 倒数第三层递归调用占了全部的 % 12.5 , 因此最后三层占了所有递归调用次数的 % 87.5 总共递归2^{h}-1次，最后一层递归次数占了全部的\%50,倒数第二层的递归调用占了全部的\%25,,倒数第三层递归调用占了全部的\%12.5,因此最后三层占了所有递归调用次数的\%87.5 总共递归2h−1次，最后一层递归次数占了全部的%50,倒数第二层的递归调用占了全部的%25,,倒数第三层递归调用占了全部的%12.5,因此最后三层占了所有递归调用次数的%87.5
当递归区间元素个数为10时，还会接着递归3层，因此我们可以进行小区间优化，当递归区间长度小于等于10时，直接进行插入排序，这样可以大大减少递归调用次数。
优化代码
void _MergeSort(int* arr, int* tmp, int begin, int end)
{
//递归终止条件--区间只有一个数
if (begin == end)
return;
//小区间优化
if (end - begin + 1 <= 10)
{
InsertSort(arr + begin, end - begin + 1);
return;
}
//将数据均分未2组
int mid = (begin + end) >> 1;
int i = begin;
//使两组均有序
_MergeSort(arr, tmp, begin, mid);
_MergeSort(arr, tmp, mid + 1, end);
//有序数组归并---归并到tmp数组中
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[i++] = arr[begin1++];
else
tmp[i++] = arr[begin2++];
}
while (begin1 <= end1) tmp[i++] = arr[begin1++];
while (begin2 <= end2) tmp[i++] = arr[begin2++];
//拷贝回元素组中
memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//归并排序
void MergeSort(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);//tmp作为临时数组存放有序数组合并后的数据
_MergeSort(arr, tmp, 0, sz - 1); //因为要借助临时数组所以构造子函数
free(tmp);
}
优化结果
算法分析
| 归并排序 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归 | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n ) O(n) O(n) |
| 非递归 | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n ) O(n) O(n) |
归并排序的应用
外排序和内排序
对内存中的数据进行排序称为内排序，对外存储器上的数据进行排序称为外排序。
现代计算机的内存通常在
8
−
16
G
B
8-16GB
8−16GB之间可以存储的整数在
21
亿
−
42
亿
21亿-42亿
21亿−42亿之间，如果我们要排
200
亿
200亿
200亿的数据量怎么处理?文章来源：https://www.toymoban.com/news/detail-586707.html
- 将数据放在文件中，将大文件分为n份小文件使每个小文件存储的数据量可以放在内存中排序
- 对将每个小文件的数据放在内存中进行排序(归并、快排)，使得每个小文件有序
- 对n个小文件外使用归并排序进行外排序
注意：
外排序只能使用归并排序，因此文件数据不能通过下标访问随机读取，文件指针习惯顺序读写，而归并排序不需要下标访问文章来源地址https://www.toymoban.com/news/detail-586707.html
到了这里，关于＜数据结构＞NO11.归并排序|递归|非递归|优化的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[数据结构 -- 手撕排序算法第七篇] 递归实现归并排序](https://imgs.yssmx.com/Uploads/2024/02/573259-1.png)
