归并排序与堆排序
归并排序与堆排序
复习定位
归并排序和堆排序都是O(n log n)的排序算法——但空间和稳定性特征不同。归并排序稳定但需要O(n)辅助空间——堆排序原地O(1)空间但不稳定。归并排序也是外部排序(处理大文件——内存放不下)的基础——通过多路归并减少了归并趟数。堆排序的建堆过程运用了自底向上调整的Floyd建堆算法——是O(n)而非直觉的O(n log n)。
归并排序
归并排序的思路——将数组分为两半——分别递归排序——然后合并两个有序子数组。合并过程中——两个子数组均已有序——通过双指针遍历辅助数组完成。
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
// 创建临时数组L[n1], R[n2]
for (int i = 0; i < n1; i++) L[i] = arr[l+i];
for (int j = 0; j < n2; j++) R[j] = arr[m+1+j];
int i=0, j=0, k=l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++]; // ≤保证了稳定性
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}归并排序的稳定性来自于合并时L[i] <= R[j]取左——等值元素优先用左边的——保持了原顺序。
归并排序的时间复杂度：递归树有log₂n层——每层合并总规模为n——总时间O(n log n)——最坏和平均都是o(n log n)。
外部排序
当数据量太大而内存无法容纳整个数据时——使用外部排序。外部排序基于归并排序——首先将大文件切分成多个可以装入内存的块——每个块在内存中用快速排序排序后写回磁盘——这些有序块称为"归并段(run)"。然后进行多路归并——每次从所有归并段的当前块中读出数据——用堆(败者树)选出最小的记录写回输出文件——直到全部数据排序完成。
败者树可以将k路归并的比较次数从每步O(k)降至O(log k)。
堆排序
堆是一个完全二叉树结构——父结点>=或<=子结点(最大堆或最小堆)。
建堆——从最后一个非叶子结点开始——自底向上调用向下调整(heapify)。因为叶子不需要调整——大约只需约n/2次堆化操作。建堆时间复杂度为O(n)而非O(n log n)——因为每一层的结点数指数递减——每个结点所需的堆化时间与树高成正比——求和后总时间为O(n)。
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}排序过程——将最大堆堆顶(最大元素)与堆末尾元素交换——堆大小减1——对新堆顶向下调整——重复n-1次——得到升序排列。堆排序不稳定——堆顶交换可能改变同值元素的相对顺序。
排序算法对比
| 算法 | 平均 | 最坏 | 空间 | 稳定 | 适用 |
|---|---|---|---|---|---|
| 归并排序 | O(n log n) | O(n log n) | O(n) | 是 | 外部排序、链表排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 | 内存受限、需快速选最值 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 否 | 通用排序(数组) |
复习检查
归并排序为什么稳定——合并过程中当L[i]==R[j]时——取左边L[i]进入排序队列——保持了相对顺序——因为L[i]在原数组中出现在R[j]之前。
Floyd建堆算法为什么是O(n)——因为最底层(结点最多)需要的堆化操作深度最小——根结点最少的结点需要深度最大——算出的总时间复杂度稳定为O(n)而不是O(n log n)——堆化操作在每个结点所花的时间与其树高尚成正比——求和被对数的错综关系抵消。
归并排序的辅助空间为什么是O(n)——每一层递归合并时——需要与被合并的两个子数组长度及另一个临时数组来处理——两层不持久的特性证明总临时空间是O(n)——不是O(n log n)。
外部排序的多路归并一次从k个归并段中选出最小的记录——如果k=1000——比较全部k个段的最小记录需要k-1=999次比较——败者树将比较次数降至约log₂k=10次——极大地降低了归并阶段的开销。
堆排序为什么不稳定——子存堆顶与末尾交换把顶点的元素移到最后——可能将跟它同值的其他元素跨到它上方的位置——破坏了原来两个等值元素的相对位置。