algorithm - 煎饼分拣

Question

我的作业有点麻烦；我的任务是想出我自己的解决方案来解决煎饼问题。

我已经把大部分代码都写下来了，除了这一部分（以下是伪代码）：

//assuming input is an array of [0...n-1] size
int maxValue = -infinity
for int i <- 0 to n-1 do
{
    for int j <-i to n-1 do
    {
       if A[j] > maxValue
       {
          maxValue <- A[j]
          maxPos <- j
    if ((maxPos == n-1) && (maxPos > i))
    {
        flip(i) //flipping starting from index i
    }
    /*the following is the bit i'm stuck on
    i know that should be able to flip the max value IN the array 
    (but not the end) to the n-1 term. 
    On the next iteration of the loop, i flip the maxValue (now held in the last 
    element) into the slot that is either at the beginning of the array, or at the
    element closest to the elements already sorted */
    maxValue <- -infinity 

抱歉，对于随机短代码，我在输入 =(.

Answer 1

我想你被困住了infinity。你可以把它当作一个large integer or long number.

Answer 2

煎饼排序：

煎饼排序是一个数学问题的通俗术语，用于按大小顺序对一堆无序的煎饼进行排序，此时可以将抹刀插入堆叠中的任何点并用于翻转上面的所有煎饼。

煎饼数是给定数量的煎饼所需的最大翻转次数。

flip(array, i)：从 0 到 i 的反转数组。

伪代码 Pancake 排序：

1) iMax = 未排序数组中最大元素的索引。

在 arr[0..unsorted_array_size -1] 中查找最大元素索引的索引。

2) 调用翻转(array, iMax)

它将数组的所有元素从 0 翻转到 iMax 索引。最大的元素将是数组中的第一个元素。

3) 调用翻转(array, unsorted_array_size -1)

翻转完整的未排序数组，结果将最大的元素放在未排序数组的末尾。

复杂性：总共执行 O(n) 次翻转操作，其中每次翻转将花费 O(n) 时间。因此复杂度为 O(n^2)。

http://javaexplorer03.blogspot.in/2015/11/pancake-sort-in-java.html