# 煎饼排序

Harshit Jindal 2023年10月12日

## 煎饼排序示例

• 第一次迭代

`mi`=4，`curr`=7

• 第二次迭代

`mi`=1，`curr`=6

• 第三次迭代

`mi`=2，`curr`=5

• 第四次迭代

`mi`=0，`curr`=4

• 第五次迭代

`mi`=2，`curr`=3

• 第六次迭代

`mi`=0，`curr`=2

## 煎饼排序算法实现

``````#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";
}
``````

## 煎饼排序算法的复杂度

### 时间复杂度

• 平均情况

``````(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2
``````

• 最坏情况

• 最佳情况

### 空间复杂度

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.