969. 煎饼排序 分类讨论+插入排序+二分查找（翻是不可能翻的）
969. 煎饼排序
给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。
一次煎饼翻转的执行过程如下：
选择一个整数 k ，1 <= k <= arr.length
反转子数组 arr[0...k-1]（下标从 0 开始）
例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。
以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pancake-sorting
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分类讨论（①②③④为重点）
1. 一共一个数
不用排序，直接返回空数组（集合）
2. 两个数（索引位置到达 i== 2）
2-1：两个数正序 1,2 不用排序
2-2：两个数倒序 2,1 需要翻转一次，长度2 ①
3. 多个数（索引位置到达 i >= 2）
3-1
arr[i] 刚好比最后一个数大，不用排序
3-2
arr[i] 比第一个数小：（234【1】），假设我们处理到 1 这一位，索引位置为 i=3 ，那么我们可以这样翻： ②
1. 翻转前面 i=3 个数字，变成为 4321 ；
2. 翻转前面 i+1 = 4 个数字，变为1234，即可有序
3-3
arr[i] 大于第一个，比最后一个数小，但是比其他数大（124【3】），假设我们处理到 3 这一位，索引位置 i=3，那么可以这样翻：③
1. 翻转前面 i+1=4 个数字，变成为 3421
2. 翻转前面 2 个数字，变成 4321
3. 翻转前面 i+1=4 个数字，变成 1234
3-4
arr[i] 比前二个或更前的数字小，大于第一个数，（134【2】），假设我们处理到 2 这一位， 前面已经处理的部分，有move个比当前数字大，当前为2，索引位置 i=3,那么可以这样翻：④
1. 翻转前面 i+1=4 个数字，变成 2431
2. 翻转前面 move+1=3 个数字，变成 3421
3. 翻转前面 move=2 个数字，变成4321
4. 翻转前面 i+1=4 个数字，变成 1234
结论
共有 ①②③④ 这四种情况需要处理，每种情况翻转次数只与 move 和 i 有关
move 可以使用二分查找找出
不用进行翻转，可以边进行插入排序，边计算出 move 值，按照上述讨论结果加入答案
方法：分类讨论+插入排序+二分查找
class Solution {public List<Integer> pancakeSort(int[] arr) {int n = arr.length;List<Integer> ans = new ArrayList<>();if(n==1)return ans;for(int i = 1; i < n; i++){if(arr[i-1]<arr[i]) continue;if(arr[i]<arr[0]){if(i==1){//①ans.add(2);}else{//②ans.add(i);ans.add(i+1);}int curr = arr[i];System.arraycopy(arr,0,arr,1,i);arr[0] = curr;}else{int left = 0;int right = i-1;while(left<right){int mid = (right-left)/2+left;if(arr[mid]>arr[i]){right = mid;}else{left = mid+1;}}if(i-right==1){//③ans.add(i+1);ans.add(2);ans.add(i+1);}else{//④int move = i-right;ans.add(i+1);ans.add(move+1);ans.add(move);ans.add(i+1);}int curr = arr[i];System.arraycopy(arr,right,arr,right+1,i-right);arr[right] = curr;}}return ans;}}