在 C 语言中，找到导致归并排序最坏情况的排列
概念
对于给定的一组元素，确定这些元素的哪种排列会导致归并排序的最坏情况？
我们知道，归并排序渐近地总是消耗 O(n log n) 时间，但在实践中，需要更多比较的情况通常会消耗更多时间。现在我们基本上需要确定输入元素的排列，该排列在执行典型的合并排序算法时会导致最大的比较次数。
示例
将下面的元素集视为已排序数组 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
导致合并排序最坏情况的结果输入数组是 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
方法
我们研究如何为输入集获取合并排序的最坏情况输入？
现在我们尝试自下而上构建数组方式
现在让排序后的数组为 {11, 12, 13, 14, 15, 16, 17, 18}。
现在，为了构建合并排序的最坏情况，导致上述排序数组的合并操作应导致最大比较。因此，合并操作中涉及的左子数组和右子数组应存储 sortedarray 的交替元素，这样，左子数组应为 {11, 13, 15, 17}，右子数组应为 {12, 14, 16, 18}。因此，数组的每个元素都将进行一次最小比较，从而导致最大比较。现在我们也为左子数组和右子数组实现相同的逻辑。对于数组 {11, 13, 15, 17}，最坏情况是其左子数组和右子数组分别为 {11, 15} 和 {13, 17}，而对于数组 {12, 14, 16, 18}，最坏情况将发生在 {12, 14} 和 {16, 18}。
完整算法
GenerateWorstCase(arr[])
现在我们创建两个辅助数组 left 和 right，并在其中存储交替的数组元素。
我们对左子数组 − 调用 GenerateWorstCase GenerateWorstCase (left)
我们为右子数组调用 GenerateWorstCase GenerateWorstCase (right)
现在我们将左子数组和右子数组的所有元素复制回原始数组。
示例
// C 程序生成归并排序的最坏情况
#include <stdlib.h>
#include <stdio.h>
// 指示打印数组的函数
void printArray(int A1[], int size1){
for (int i = 0; i < size1; i++)
printf("%d ", A1[i]);
printf("
");
}
// 表示连接左子数组和右子数组的函数
int join(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
int i; // 因此在第二个循环中使用
for (i = 0; i <= m1 - l1; i++)
arr1[i] = left1[i];
for (int j = 0; j < r1 - m1; j++)
arr1[i + j] = right1[j];
}
// 表示函数在左
// 和右子数组中存储交替元素
int split(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
for (int i = 0; i <= m1 - l1; i++)
left1[i] = arr1[i * 2];
for (int i = 0; i < r1 - m1; i++)
right1[i] = arr1[i * 2 + 1];
}
// 表示生成归并排序最坏情况的函数
int generateWorstCase(int arr1[], int l1, int r1){
if (l1 < r1){
int m1 = l1 + (r1 - l1) / 2;
// 创建两个辅助数组
int left1[m1 - l1 + 1];
int right1[r1 - m1];
// 在左子数组中存储交替数组元素
// 和右子数组中存储交替数组元素
split(arr1, left1, right1, l1, m1, r1);
// 递归第一半和第二半
generateWorstCase(left1, l1, m1);
generateWorstCase(right1, m1 + 1, r1);
// 连接左子数组和右子数组
join(arr1, left1, right1, l1, m1, r1);
}
}
// 驱动程序代码
int main(){
// 初始化排序数组
int arr1[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
printf("排序后的数组为
");
printArray(arr1, n1);
// 生成归并排序的最坏情况
generateWorstCase(arr1, 0, n1 - 1);
printf("
导致合并排序最坏情况的输入数组为
");
printArray(arr1, n1);
return 0;
}
输出
排序后的数组为 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 导致合并排序最坏情况的输入数组为 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
