煎饼排序
入门理解"翻转操作"如何实现排序，面试常考。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void flip(int arr[], int i) {
2 int left = 0;
3 while (left < i) { swap(arr[left], arr[i]); left++; i--; }
4}
5
6void pancakeSort(int arr[], int n) {
7 for (int size = n; size > 1; size--) {
8 int maxIdx = 0;
9 for (int i = 1; i < size; i++)
10 if (arr[i] > arr[maxIdx]) maxIdx = i;
11 if (maxIdx != size - 1) {
12 flip(arr, maxIdx);
13 flip(arr, size - 1);
14 }
15 }
16}
复杂度分析
时间 O(n²)
空间 O(1)
最优 O(n)
最坏 O(n²)
算法讲解
煎饼排序只能执行一种操作：翻转数组的前 k 个元素。
策略是每次找到当前最大值，翻转它到顶部，再翻转到正确位置。
最多需要 2n-3 次翻转，是理论上翻转次数最少的算法。
它是理解"受限操作集"下排序策略的经典问题。