归并排序
归并排序(Merge Sort)是一种分治法思想的高效排序算法。其基本思想是:将序列递归地分成两半,分别排序后再合并成一个有序序列。
点击“执行一步”观察算法状态变化。
- 将序列递归分成两半,直到每个子序列只有一个元素
- 两两合并子序列,合并时按顺序归并成有序序列
- 重复合并直到全部有序
伪代码如下:
function mergeSort(A, left, right):
if left < right:
mid = (left + right) // 2
mergeSort(A, left, mid)
mergeSort(A, mid+1, right)
merge(A, left, mid, right)
function merge(A, left, mid, right):
创建临时数组tmp
i = left, j = mid+1, k = 0
while i <= mid and j <= right:
if A[i] <= A[j]:
tmp[k++] = A[i++]
else:
tmp[k++] = A[j++]
复制剩余元素到tmp
将tmp复制回A[left..right]
// 合并两个有序区间 A[left..mid] 和 A[mid+1..right]
void Merge(int A[], int left, int mid, int right) {
int n1 = mid - left + 1, n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = A[left + i];
for (int j = 0; j < n2; j++) R[j] = A[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) A[k++] = L[i++];
else A[k++] = R[j++];
}
while (i < n1) A[k++] = L[i++]; // 复制剩余
while (j < n2) A[k++] = R[j++];
}
void MergeSort(int A[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
MergeSort(A, left, mid); // 左半排序
MergeSort(A, mid + 1, right); // 右半排序
Merge(A, left, mid, right); // 合并
}
}
自然归并排序
与标准归并(固定对半划分)不同,自然归并先扫描找出序列中已有的有序子段(天然有序的”run”),直接对这些子段进行归并,减少归并趟数,尤其适合数据局部有序的场景。
- 最好/最坏/平均情况:
- 空间复杂度:
- 稳定性:稳定排序
习题 1
对数组 进行归并排序,写出第一次归并后的结果。
解题思路:
本题考查归并排序的第一次归并。核心思想是先把序列两两分组视作初始归并段,再把相邻归并段有序地合并起来;第一次归并处理的对象正是最初的两两分组。
详细步骤:
- 初始分组:[8,4],[5,7],[1,3],[6,2]
- 第一次归并:[4,8],[5,7],[1,3],[2,6]
- 校验:第一次归并后得到的每个长度为 2 的分组内部都已经有序,可以直接作为下一轮归并的输入。
最终答案:
如上,第一次归并后每组有序。
习题 2
归并排序的时间复杂度和空间复杂度分别是多少?
解题思路:
本题考查归并排序的复杂度分析。归并排序共需 趟合并,每趟合并的总代价是 ,故时间复杂度为 ;由于需要与原序列等长的辅助数组来存放合并结果,空间复杂度为 。
详细步骤:
- 时间复杂度 :共 趟合并,每趟代价 。
- 空间复杂度 :需要与原序列等长的辅助数组存放合并结果,不是原地排序。
- 对比参考:快速排序平均时间复杂度为 、空间为 (递归栈);堆排序时间复杂度恒为 、空间为 。
最终答案:
时间 ,空间 。
