C ++中的煎饼分类

假设我们有一个数组A，我们将对A执行Pancake排序技术。这里的主要约束是我们只能使用一个称为rev(arr,i)的操作。这会将arr的元素从0反转到第i个位置。这个想法就像选择排序。我们反复将max元素放在最后以减小数组的大小。因此，如果输入像[54,85,52,25,98,75,25,11,68]，那么结果将是[11,25,25,52,54,68,75,85,98]

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

• 大小：= n

• 当大小> 1时，执行

• index：=从[0到size – 1]的arr中最大元素的索引

• rev(arr,index)

• rev(arr,size-1)

• 大小：=大小-1

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

示例

#include<iostream>
using namespace std;
void rev(int arr[], int i) {
   int temp, st = 0;
   while (st < i) {
      temp = arr[st];
      arr[st] = arr[i];
      arr[i] = temp;
      st++;
      i--;
   }
}
int maxIndex(int arr[], int n) {
   int index, i;
   for (index = 0, i = 0; i < n; ++i){
      if (arr[i] > arr[index]) {
         index = i;
      }
   }
   return index;
}
int pancakeSort(int arr[], int n) {
   for (int size = n; size > 1; size--) {
      int index = maxIndex(arr, size);
      if (index != size-1) {
         rev(arr, index);
         rev(arr, size-1);
      }
   }
}
int main() {
   int arr[] = {54, 85, 52, 25, 98, 75, 25, 11, 68};
   int n = sizeof(arr)/sizeof(arr[0]);
   pancakeSort(arr, n);
   cout << "Sorted array: ";
   for (int i = 0; i < n; ++i)
   cout << arr[i] << " ";
}

输入值

[54, 85, 52, 25, 98, 75, 25, 11, 68]

输出结果

[11,25,25,52,54,68,75,85,98]