我们可以先找到最大的数的位置i,然后煎饼翻转k= i+1,让最大的数放到最前面。
接着我们煎饼翻转len,让最大的数放到最后面,然后len --。
接着我们再找到arr[0~-2]中最大的数,执行操作1~2即可,一直执行到i=2为止。
对于煎饼翻转的过程:如果我们的翻转数为k,我们先定一个最小下标a=0, 执行swap(arr[a],arr[k-1]),进行数据交换,然后执行a ++,b --即可。直到a>=b为止,视为完成了煎饼翻转的过程。
示例代码:
package main
import "fmt"
func main() {
list := data{28, 11, 59, -26, 503, 158, 997, 193, -23, 44}
fmt.Println("\n--- Unsorted --- \n\n", list)
list.pancakesort()
fmt.Println("\n--- Sorted ---\n\n", list, "\n")
}
type data []int32
func (dataList data) pancakesort() {
for uns := len(dataList) - 1; uns > 0; uns-- {
// find largest in unsorted range
lx, lg := 0, dataList[0]
for i := 1; i <= uns; i++ {
if dataList[i] > lg {
lx, lg = i, dataList[i]
}
}
// move to final position in two flips
dataList.flip(lx)
dataList.flip(uns)
}
}
func (dataList data) flip(r int) {
for l := 0; l < r; l, r = l+1, r-1 {
dataList[l], dataList[r] = dataList[r], dataList[l]
}
}
输出:
--- Unsorted ---
[28 11 59 -26 503 158 997 193 -23 44]
--- Sorted ---
[-26 -23 11 28 44 59 158 193 503 997]