煎饼分拣

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 

对不起，对于随机短码，当我输入=(时，我过早地按下了sumbit。

Answer 1

我觉得你被infinity卡住了。你可以把它当做一个large integer or long number。

Answer 2

薄煎饼排序：

煎饼分拣是数学问题的俗称，指的是将一堆杂乱的煎饼按大小排序，此时可以将刮刀插入到煎饼堆中的任何一点，并用来翻转上面的所有煎饼。

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

数组翻转(，i)：将数组从0反转到i。

伪码煎饼排序：

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

在arr0..unsorted_array_size -1中查找最大元素索引的索引。

数组2)调用(数组，iMax)

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

数组3)调用(，unsorted_array_size -1)

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

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

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