煎餅排序基本資訊

煎餅排序是數量問題的口語術語,當刮刀可以插入堆疊中的任何點並用於翻轉其上方的所有薄餅時,按照尺寸的順序對無序堆疊的薄煎餅進行分類。煎餅數是給定數量的煎餅所需的最小翻轉數。

與傳統的排序演算法不同,傳統的排序演算法試圖以儘可能少的比較進行排序,目標是儘可能少地對序列進行排序。

這個想法是做類似於選擇排序的事情。我們一個接一個地放置最後一個元素,並將當前陣列的大小減少一個。

解剖問題:

  1. 需要從最小(頂部)到最大(底部)訂購煎餅,起始堆可以按任何順序排列。
  2. 我只能執行翻轉翻轉整個堆疊。
  3. 要將特定的煎餅翻轉到堆疊的底部,我們首先必須將其翻轉到頂部(然後再將其翻轉到底部)。
  4. 要訂購每個煎餅,需要一個翻轉到頂部,一個翻轉到最終位置。

直覺演算法:

  1. 找到最大的亂序煎餅並將其翻轉到底部(你可能需要先將其翻轉到堆疊的頂部)。

  2. 重複步驟 1,直到訂購堆疊。

  3. 就是這樣,兩步演算法將起作用。

煎餅排序演算法示例:

https://i.stack.imgur.com/SDjwT.gif

輔助空間: O(1)
時間複雜度: O(n^2)