10. 实现归并排序¶
10.1. 实现归并排序¶
实现归并排序会遇到若干技术上的困难。
第一个决定是如何表示线性表。
归并排序很适合对单向链表排序，因为归并并不需要对线性表元素
进行随机访问。
因此，当输入以链表形式给出时，归并排序是首选方法。
为链表实现 merge 很直接，因为我们只需从输入线性表的前端
取出元素，再追加到输出线性表。
把输入线性表拆成两个相等的半部分则有些困难。
理想情况下，我们只需把线性表拆成前半和后半。
然而，即使事先知道线性表的长度，仍然需要遍历链表的一半才能
到达后半部分的起点。
有一种更简单的方法，它不依赖于事先知道线性表的长度，而是把
输入线性表的元素交替地分配到两个子线性表中。
第一个元素分给第一个子线性表，第二个元素分给第二个子线性表，
第三个分给第一个子线性表，第四个分给第二个子线性表，依此类推。
这需要完整地遍历输入线性表一趟来构建这些子线性表。
当归并排序的输入是数组时，只要知道数组边界，把输入拆成两个 子数组就很容易。 如果把子数组归并到第二个数组，归并也很容易。 注意，这种做法所需的空间是前面介绍过的任何排序方法的两倍， 这对归并排序来说是一个严重缺点。 不借助第二个数组也可以归并子数组，但要高效地做到这一点极其 困难，实际上并不实用。 把两个子数组合并到第二个数组虽然实现简单，却带来另一个困难： 归并过程结束时，有序线性表位于辅助数组中。 想一想归并排序的递归特性是如何把原数组拆成子数组的。 归并排序被递归调用，直到创建出长度为 1 的子数组，这需要 \(\log n\) 层递归。 这些子数组被归并为长度为 2 的子数组，后者又被归并为长度为 4 的子数组，依此类推。 我们需要避免每次归并操作都要求一个新数组。 经过一番努力，可以设计出一种在两个数组之间交替的算法。 更简单的做法是先把已排序的子线性表复制到辅助数组，再把它们 归并回原数组。
下面是遵循这一做法的完整归并排序实现。
输入记录存放在数组 A 中。
数组 temp 用于在归并过程中临时复制记录。
参数 left 和 right 分别定义待排序子数组的左、右下标。
对 mergesort 的初始调用为
mergesort(array, temparray, 0, n-1) 。
void mergesort(int[] A, int[] temp, int left, int right) {
if (left == right) { return; } // List has one record
int mid = (left+right)/2; // Select midpoint
mergesort(A, temp, left, mid); // Mergesort first half
mergesort(A, temp, mid+1, right); // Mergesort second half
for (int i=left; i<=right; i++) { // Copy subarray to temp
temp[i] = A[i];
}
// Do the merge operation back to A
int i1 = left;
int i2 = mid + 1;
for (int curr = left; curr <= right; curr++) {
if (i1 == mid+1) { // Left sublist exhausted
A[curr] = temp[i2++];
}
else if (i2 > right) { // Right sublist exhausted
A[curr] = temp[i1++];
}
else if (temp[i1] < temp[i2]) { // Get smaller value
A[curr] = temp[i1++];
}
else{
A[curr] = temp[i2++];
}
}
}
void mergesort(T[] A, T[] temp, int left, int right) {
if (left == right) { return; } // List has one record
int mid = (left+right)/2; // Select midpoint
mergesort(A, temp, left, mid); // Mergesort first half
mergesort(A, temp, mid+1, right); // Mergesort second half
for (int i=left; i<=right; i++) { // Copy subarray to temp
temp[i] = A[i];
}
// Do the merge operation back to A
int i1 = left;
int i2 = mid + 1;
for (int curr = left; curr <= right; curr++) {
if (i1 == mid+1) { // Left sublist exhausted
A[curr] = temp[i2++];
}
else if (i2 > right) { // Right sublist exhausted
A[curr] = temp[i1++];
}
else if (temp[i1].compareTo(temp[i2]) <= 0) { // Get smaller value
A[curr] = temp[i1++];
}
else{
A[curr] = temp[i2++];
}
}
}
void mergesort(Comparable* A[], Comparable* temp[], int left, int right) {
if (left == right) return; // List has one record
int mid = (left + right)/2; // Select midpoint
mergesort(A, temp, left, mid); // Mergesort first half
mergesort(A, temp, (mid+1), right); // Mergesort second half
for (int i = left; i <= right; i++) // Copy subarray to temp
*temp[i] = *A[i];
// Do the merge operation back to A
int i1 = left;
int i2 = mid + 1;
for (int curr = left; curr <= right; curr++) {
if (i1 == mid+1) // Left sublist exhausted
*A[curr] = *temp[i2++];
else if (i2 > right) // Right sublist exhausted
*A[curr] = *temp[i1++];
else if (*temp[i1] <= *temp[i2]) // Get smaller value
*A[curr] = *temp[i1++];
else
*A[curr] = *temp[i2++];
}
}
下面是归并步骤的可视化。
下面展示一个优化过的归并排序实现。
它在初始复制时反转第二个子数组的顺序。
这样，两个子数组的当前位置从两端向内推进，使每个子数组的末端
可以充当另一个的哨兵。
与前一实现不同，这里无需测试两个子数组中何时有一个变为空。
这个版本还有第二项优化：
当数组长度小于 THRESHOLD 定义的值时，它使用插入排序来对
小数组排序。
void mergesortOpt(int[] A, int[] temp, int left, int right) {
int i, j, k, mid = (left+right)/2; // Select the midpoint
if (left == right) { return; } // List has one record
if ((mid-left) >= THRESHOLD) { mergesortOpt(A, temp, left, mid); }
else { inssort(A, left, mid); }
if ((right-mid) > THRESHOLD) { mergesortOpt(A, temp, mid+1, right); }
else { inssort(A, mid+1, right); }
// Do the merge operation. First, copy 2 halves to temp.
for (i=left; i<=mid; i++) { temp[i] = A[i]; }
for (j=right; j>mid; j--) { temp[i++] = A[j]; }
// Merge sublists back to array
for (i=left,j=right,k=left; k<=right; k++) {
if (temp[i] < temp[j]) { A[k] = temp[i++]; }
else {
A[k] = temp[j--];
}
}
}
void mergesortOpt(T[] A, T[] temp, int left, int right) {
int i, j, k, mid = (left+right)/2; // Select the midpoint
if (left == right) { return; } // List has one record
if ((mid-left) >= THRESHOLD) { mergesortOpt(A, temp, left, mid); }
else { inssort(A, left, mid); }
if ((right-mid) > THRESHOLD) { mergesortOpt(A, temp, mid+1, right); }
else { inssort(A, mid+1, right); }
// Do the merge operation. First, copy 2 halves to temp.
for (i=left; i<=mid; i++) { temp[i] = A[i]; }
for (j=right; j>mid; j--) { temp[i++] = A[j]; }
// Merge sublists back to array
for (i=left,j=right,k=left; k<=right; k++) {
if (temp[i].compareTo(temp[j]) <= 0) { A[k] = temp[i++]; }
else {
A[k] = temp[j--];
}
}
}
void mergesortOpt(Comparable* A[], Comparable* temp[], int left, int right) {
int i, j, k, mid = (left+right)/2;// Select the midpoint
if (left == right) return; // List has one record
if ((mid-left) >= THRESHOLD) mergesortOpt(A, temp, left, mid);
else inssort(A, left, mid);
if ((right-mid) > THRESHOLD) mergesortOpt(A, temp, mid+1, right);
else inssort(A, mid+1, right);
// Do the merge operation. First, copy 2 halves to temp.
for (i=left; i<=mid; i++) *temp[i] = *A[i];
for (j=right; j>mid; j--) *temp[i++] = *A[j];
// Merge sublists back to array
for (i=left,j=right,k=left; k<=right; k++)
if (*temp[i] <= *temp[j]) *A[k] = *temp[i++];
else *A[k] = *temp[j--];
}
下面是优化后归并步骤的可视化。
