煎饼排序
煎饼排序是一种基于反转的排序算法。它是基于现实生活中的问题，即借助铲子在盘子上类似于摊煎饼。它的名字来源于算法中使用的翻转操作，类似于翻转煎饼。与大多数排序算法试图最小化执行排序所需的比较次数不同，它试图以最小的反转次数对数组进行排序。就像选择排序一样，它也将最大元素放在最后。
煎饼排序算法
假设我们有一个包含 n 元素的未排序数组 A[]。
PancakeSort()
-
初始化未排序子数组的大小为
curr = n-1，并迭代减少其大小1。 -
查找未排序子数组中最大元素
mi的索引。 -
使用
flip(A,mi)翻转A[0, ... , mi]，将最大元素A[i]移动到索引0处。 -
使用
flip(A,i)将最大元素A[i]移动到正确的位置，翻转A[0, ... , i]。
Flip()
-
将第一个索引
f的元素与最后一个索引e的元素互换。 -
增加
f，减少e。 -
重复以上步骤，直到
f <= e。
煎饼排序示例
假设我们有一个数组：(3, 5, 2, 1, 7, 6, 4)。我们将使用煎饼排序算法对其进行排序。
- 第一次迭代
mi=4，curr=7
| 翻转(mi) | [7, 1, 2, 5, 3, 6, 4] |
| 翻转(6) | [ 4, 6, 3, 5, 2, 1, 7] |
- 第二次迭代
mi=1，curr=6
| 翻转(mi) | [6, 4, 3, 5, 2, 1, 7] |
| 翻转(5) | [1, 2, 5, 3, 4, 6, 7] |
- 第三次迭代
mi=2，curr=5
| 翻转(mi) | [5, 2, 1, 3, 4, 6, 7] |
| 翻转(4) | [4, 3, 1, 2, 5, 6, 7] |
- 第四次迭代
mi=0，curr=4
| 翻转(mi) | [4, 3, 1, 2, 5, 6, 7] |
| 翻转(3) | [2, 1, 3, 4, 5, 6, 7] |
- 第五次迭代
mi=2，curr=3
| 翻转(mi) | [3, 1, 2, 4, 5, 6, 7] |
| 翻转(2) | [2, 1, 3, 4, 5, 6, 7] |
- 第六次迭代
mi=0，curr=2
| 翻转(mi) | [2, 1, 3, 4, 5, 6, 7] |
| 翻转(1) | [1, 2, 3, 4, 5, 6, 7] |
我们得到最终的排序数组为 1，2，3，4，5，6，7。
煎饼排序算法实现
#include <bits/stdc++.h>
using namespace std;
void flip(int arr[], int i) {
int temp, start = 0;
while (start < i) {
temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i--;
}
}
int findMax(int arr[], int n) {
int mi = 0;
for (int i = 0; i < n; ++i)
if (arr[i] > arr[mi]) mi = i;
return mi;
}
void pancakeSort(int arr[], int n) {
for (int i = n; i > 1; i--) {
int mi = findMax(arr, i);
if (mi != i - 1) {
flip(arr, mi);
flip(arr, i - 1);
}
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
pancakeSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
煎饼排序算法的复杂度
时间复杂度
- 平均情况
平均来说，在煎饼排序的第 i 次传递中会进行 n-i 次比较。所以，如果有 n 次迭代，那么平均时间复杂度可以用下式来表示。
(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2
因此，时间复杂度为 [Big Theta]：O(n2)。也可以通过计算循环次数来计算。总共有两个循环的 n 次迭代，使得复杂度：n*n = n2。
- 最坏情况
最坏的情况发生在小元素和大元素交替的时候。共需要 2n-3 次翻转。所需的翻转次数为 O(n)。最坏情况下的时间复杂度为 [Big O]：O(n2)。
- 最佳情况
最好的情况是数组已经排序，不需要翻转。最佳情况下的时间复杂度是 [Big Omega]：O(n)。
空间复杂度
这个算法的空间复杂度是 O(n)，因为除了一个临时变量外，不需要额外的内存。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn