时间复杂度
《算法导论》2.3.1 分治法。
归并排序采用了分治法的递归排序。分治法:分解子问题,解决子问题,合并子结果。
分解:分解待排序的
个元素的序列各成
个元素的子列。
解决:使用归并排序递å归地排序两个子序列。
合并:合并两个已排序的子序列以产生已排序的答案。
因为排序数组会被 拆开,归并排序时间复杂度稳定的
。
![](https://img.haomeiwen.com/i4321487/662edd53b262e9b5.png)
相对于其它的 排序,它需要额外的临时空间辅助,有一定的资源损耗。小数量级(百万级别)的排序,要比快速排序慢。但是大数量级数据(千万级别),因为归并排序树深最小,排序比快速排序快。
快速排序,最优算法复杂度,数组会被
拆开。实际操作中数据很难达到最优。而归并一直都是通过
进行拆分。
算法
算法导论实现思想
- 拆分左右两个临时数组,临时数组最后是一个∞无穷大的数字。
- 两个子数组进行比较,小的数值会拷贝到原数组。
![](https://img.haomeiwen.com/i4321487/193e2e664f3b89a4.png)
![](https://img.haomeiwen.com/i4321487/9710daa62ff6e39e.png)
实现
实际实现,通过一个辅助数组进行实现(源码)。
void merge_sort(int array[], int start, int mid, int end) {
int k = 0;
int low = start;
int high = mid + 1;
int* temp = (int*)malloc(sizeof(int) * (end - start + 1));
while (low <= mid && high <= end) {
(array[low] < array[high]) ? temp[k++] = array[low++]
: temp[k++] = array[high++];
}
while (high <= end) temp[k++] = array[high++];
while (low <= mid) temp[k++] = array[low++];
for (int i = 0; i < k; i++) array[start + i] = temp[i];
free(temp);
}
void merge(int array[], int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
merge(array, start, mid);
merge(array, mid + 1, end);
merge_sort(array, start, mid, end);
}
实现流程
数组 A = {5, 2,4,7, 1, 3, 2, 6} 子数组最后一次合并排序流程。
![](https://img.haomeiwen.com/i4321487/abecaeb7c8adfa9c.png)
参考
快速排序、归并排序、堆排序三种算法性能比较
《算法导论》(第三版)
更精彩内容,请关注我的博客:https://wenfh2020.com
网友评论