数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学查找导致 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}。
现在为了构建归并排序的最坏情况，导致上述已排序数组的合并操作应产生最大的比较次数。因此，参与合并操作的左子数组和右子数组应存储已排序数组的交替元素，使得左子数组为 {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 program to generate Worst Case of Merge Sort
#include <stdlib.h>
#include <stdio.h>
// Indicates function to print an array
void printArray(int A1[], int size1){
for (int i = 0; i < size1; i++)
printf("%d ", A1[i]);
printf("
");
}
// Indicates function to join left and right subarray
int join(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
int i; // So used in second loop
for (i = 0; i <= m1 - l1; i++)
arr1[i] = left1[i];
for (int j = 0; j < r1 - m1; j++)
arr1[i + j] = right1[j];
}
// Indicates function to store alternate elemets in left
// and right subarray
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];
}
// Indicates function to generate Worst Case of Merge Sort
int generateWorstCase(int arr1[], int l1, int r1){
if (l1 < r1){
int m1 = l1 + (r1 - l1) / 2;
// creating two auxillary arrays
int left1[m1 - l1 + 1];
int right1[r1 - m1];
// Storing alternate array elements in left
// and right subarray
split(arr1, left1, right1, l1, m1, r1);
// Recursing first and second halves
generateWorstCase(left1, l1, m1);
generateWorstCase(right1, m1 + 1, r1);
// joining left and right subarray
join(arr1, left1, right1, l1, m1, r1);
}
}
// Driver code
int main(){
// Initializes sorted array
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("Sorted array is
");
printArray(arr1, n1);
// generating worst Case of Merge Sort
generateWorstCase(arr1, 0, n1 - 1);
printf("
Input array that will result in " "worst case of merge sort is
");
printArray(arr1, n1);
return 0;
}输出
Sorted array is 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Input array that will result in worst case of merge sort is 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
249 次浏览
