在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("</p><p>");
}
// 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 </p><p>");
   printArray(arr1, n1);
   // generating worst Case of Merge Sort
   generateWorstCase(arr1, 0, n1 - 1);
   printf("</p><p>Input array that will result in " "worst case of merge sort is </p><p>");
   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

以上是在C语言中找到导致归并排序最坏情况的排列的详细内容。更多信息请关注PHP中文网其他相关文章！