查找导致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]。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数merge()，它将使用数组arr，数组左，数组右，l_index，m_index，r_index，

• 对于初始化i：= 0，当i <= m_index-l_index时，更新（将i增加1），执行-

• arr [i]：=左[i]

• 对于初始化j：= 0，当j <r_index-m_index，更新（j增加1），-

• arr [i + j] =右[j]

• 定义一个函数divide()，它将使用数组arr，数组左，数组右，l_index，m_index，r_index，

• 对于初始化i：= 0，当i <= m_index-l_index时，更新（将i增加1），执行-

• left [i]：= arr [i * 2]

• 对于初始化i：= 0，当i <r_index-m_index时，更新（将i增加1），执行-

• right [i]：= arr [i * 2 +1]

• 定义一个函数gen_worst_seq()，它将使用数组arr []，l_index，r_index，

• 如果l_index <r_index，则-

• m_index：= l_index +(r_index-l_index)/ 2

• 定义一个左边的数组，大小为：m_index-l_index + 1。

• 定义大小为r_index-m_index的数组权限。

• 除法(arr,left,right,l_index,m_index,r_index)

• gen_worst_seq(left,l_index,m_index)

• gen_worst_seq（right，m_index + 1，r_index）

• 合并(arr,left,right,l_index,m_index,r_index)

例 

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
void display(int A[], int size) {
   for (int i = 0; i < size; i++)
      cout << A[i] << " ";
   cout << endl;
}
int merge(int arr[], int left[], int right[],int l_index, int m_index, int r_index) {
   int i;
   for (i = 0; i <= m_index - l_index; i++)
      arr[i] = left[i];
   for (int j = 0; j < r_index - m_index; j++)
      arr[i + j] = right[j];
}
int divide(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
   for (int i = 0; i <= m_index - l_index; i++)
      left[i] = arr[i * 2];
   for (int i = 0; i < r_index - m_index; i++)
      right[i] = arr[i * 2 + 1];
}
int gen_worst_seq(int arr[], int l_index, int r_index) {
   if (l_index < r_index) {
      int m_index = l_index + (r_index - l_index) / 2;
      int left[m_index - l_index + 1];
      int right[r_index - m_index];
      divide(arr, left, right, l_index, m_index, r_index);
      gen_worst_seq(left, l_index, m_index);
      gen_worst_seq(right, m_index + 1, r_index);
      merge(arr, left, right, l_index, m_index, r_index);
   }
}
int main() {
   int arr[] = {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
   int n = sizeof(arr) / sizeof(arr[0]);
   gen_worst_seq(arr, 0, n - 1);
   display(arr, 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