翻烙餅問(wèn)題是非常經(jīng)典的問(wèn)題, 星期五的晚上, 一幫同事在希格瑪大廈附近的硬盤(pán)酒吧多喝了幾杯程序員多喝了幾杯之后談什么呢? 自然是算法問(wèn)題有個(gè)同事說(shuō):
我以前在餐館打工, 顧客經(jīng)常點(diǎn)非常多的烙餅店里的餅大小不一, 我習(xí)慣在到達(dá)顧客飯桌前, 把一摞餅按照大小次序擺好小的在上面, 大的在下面由于我一只手托著盤(pán)子, 只好用另一只手, 一次抓住最上面的幾塊餅, 把它們上下顛倒個(gè)個(gè)兒, 反復(fù)幾次之后, 這摞烙餅就排好序了
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));
}
/**
* 遞歸翻轉(zhuǎn)排序
* @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);
}
/**
* 翻轉(zhuǎn)
* @param arr 餅
* @param endPos 從 0 ~ endPos 處開(kāi)始翻轉(zhuǎn)
*/
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 中獲取最大的餅的下標(biāo)
* @param arr 餅
* @param endPos 結(jié)束位置
* @return 最大下標(biāo)
*/
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;
}
}
