翻烙饼问题是非常经典的问题, 星期五的晚上, 一帮同事在希格玛大厦附近的硬盘酒吧多喝了几杯程序员多喝了几杯之后谈什么呢? 自然是算法问题有个同事说:
我以前在餐馆打工, 顾客经常点非常多的烙饼店里的饼大小不一, 我习惯在到达顾客饭桌前, 把一摞饼按照大小次序摆好小的在上面, 大的在下面由于我一只手托着盘子, 只好用另一只手, 一次抓住最上面的几块饼, 把它们上下颠倒个个儿, 反复几次之后, 这摞烙饼就排好序了
import java.util.Arrays;
public class Pizza {
public static void main(String[] args) {
//一堆饼
int[] arr = {5, 6, 1, 3, 2, 8};
sort(arr, arr.length);
System.out.println(Arrays.toString(arr));
}
/**
* 递归翻转排序
* @param arr 饼
* @param endPos 从 0 ~ endPos 处排序
*/
static void sort(int[] arr, int endPos) {
if (endPos == 0) {
return;
}
int maxIndex = getMaxIndex(arr, endPos);
reverse(arr, maxIndex);
reverse(arr, endPos - 1);
endPos--;
sort(arr, endPos);
}
/**
* 翻转
* @param arr 饼
* @param endPos 从 0 ~ endPos 处开始翻转
*/
static void reverse(int[] arr, int endPos) {
int startPos = 0;
int temp;
while (startPos < endPos) {
temp = arr[startPos];
arr[startPos] = arr[endPos];
arr[endPos] = temp;
startPos++;
endPos--;
}
}
/**
* 从 0 ~ endPos 中获取最大的饼的下标
* @param arr 饼
* @param endPos 结束位置
* @return 最大下标
*/
static int getMaxIndex(int[] arr, int endPos) {
int maxIndex = 0;
for (int i = 0; i < endPos; i++) {
maxIndex = i;
for (int j = 0; j < endPos; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
}
return maxIndex;
}
}
