选择与归并

• 简单选择排序：
  • 第 $i$ 趟从 $n-i+1$ 个记录中选最小的与第 $i$ 个交换。
  • 特点：移动次数最少（最多 $3(n-1)$ 次）。
  • 不稳定。
• 归并排序：
  • 思想：分治法。将两个有序表合并成一个。
  • 特点：稳定。时间 $O(n\log n)$。
  • 缺点：需要 $O(n)$ 的辅助空间。

// 数组：arr[low...high]
void MergeSort3Way(int arr[], int low, int high, int dest[]) {
    // 递归出口：如果只有一个元素或没有元素，直接返回
    if (low >= high) return;
 
    // 1. 计算两个切分点，把区间 [low, high] 平分成三份
    int mid1 = low + (high - low) / 3;
    int mid2 = low + 2 * (high - low) / 3;
 
    // 2. 递归：把三份分别排好序
    MergeSort3Way(arr, low, mid1, dest);
    MergeSort3Way(arr, mid1 + 1, mid2, dest);
    MergeSort3Way(arr, mid2 + 1, high, dest);
 
    // 3. 合并：把三个排好序的子序列合为一个
    Merge(arr, low, mid1, mid2, high, dest);
}

int i = low, j = mid1 + 1, k = mid2 + 1, l = low;
 
while (i <= mid1 && j <= mid2 && k <= high) {
    if (arr[i] < arr[j]) {
        if (arr[i] < arr[k]) dest[l++] = arr[i++]; // i 最小
        else dest[l++] = arr[k++];                // k 最小
    } else {
        if (arr[j] < arr[k]) dest[l++] = arr[j++]; // j 最小
        else dest[l++] = arr[k++];                // k 最小
    }
}
......