搜尋演算法Sorting algorithm

介紹原因
因為icebear在搜尋過程中會將人氣質較高的料理排在搜尋結果的前半段，所以需要用到排序演算法，因此icebear在這裡介紹幾個常見的演算法。

• 簡介
  排序演算法是一種能將一串資料依照特定排序方式進行排列的演算法，最常用到的排序方式是數值順序以及字典順序。
  有效的排序演算法在像是搜尋演算法與合併演算法中非常重要，才能讓這些演算法得到正解。
  排序演算法也用在處理文字資料以及產生人類可讀的輸出結果。排序演算法的輸出必須遵守下列兩個基本原則：
  • 輸出結果為遞增或遞減序列
  • 輸出結果是原輸入的一種排列、或是重組

• 排序法分類
  • 時間複雜度 : 依據串列（list）的大小(n)計算最差、平均、和最好表現。一般而言，好的表現是O(nlogn)，壞的表現是O(n^2)。
    一個排序理想的表現是O(n)，但平均而言不可能達到。基於比較的排序演算法對大多數輸入而言至少需要O(nlogn)。使用具有強大計算能力的計算機，能令時間複雜度趨近於O(n),但不等於O(n)。
  • 記憶體使用量
  • 穩定性：穩定的排序演算法會讓原本有相等鍵值的紀錄維持相對次序。也就是當紀錄X=Y，且在原本的串列中X出現在Y之前時，在排序過的串列中X也將會是在Y之前。
  • 其他 : 依據排序的方法：插入、交換、選擇、合併等等。

• 常見排序演算法

  • 泡沫排序(BubbleSort)

    • 資料物件 :陣列
    • 穩定性 : 陣列(Y)
    • 時間複雜度 :
      • 平均 : O(n^2)
      • 額外空間複雜度 :O(1)
    • 運作方式 :
      1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
      2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
      3. 針對所有的元素重複以上的步驟，除了最後一個。
      4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較

  • 選擇排序 (Selectionsort)

    • 資料物件 :陣列、鏈結串列
    • 穩定性 :陣列(N)、鏈結串列(Y)
    • 時間複雜度 :
      • 平均 : O(n^2)
      • 額外空間複雜度 :O(1)
    • 運作方式 :
      首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
      然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
      以此類推，直到所有元素均排序完畢。

  • 插入排序(InsertionSort)

    • 資料物件 : 陣列、鏈結串列
    • 穩定性 : 陣列(Y)、鏈結串列(Y)
    • 時間複雜度 :
      • 平均 : O(n^2)
      • 額外空間複雜度 :O(1)
    • 運作方式 :
      1. 從第一個元素開始，該元素(A)可以認為已經被排序
      2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
      3. 如果A大於新元素，將A移到下一位置
      4. 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置(X)
      5. 將新元素插入到X後
      6. 重複步驟2~5

  • 堆積排序(HeapSort)

    • 資料物件 :陣列
    • 穩定性 : 陣列(N)
    • 時間複雜度 :
      • 平均:O(nlogn)
      • 額外空間複雜度 :O(1)
    • 運作方式 :
      在堆積的資料結構中，堆積中的最大值總是位於根節點（在優先佇列中使用堆積的話堆積中的最小值位於根節點）。堆積中定義以下幾種操作：
    • 最大堆積調整（Max Heapify）：將堆積的末端子節點作調整，使得子節點永遠小於父節
    • 建立最大堆積（Build Max Heap）：將堆積中的所有數據重新排序
    • 堆積排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆積調整的遞迴運算

  • 合併排序(MergeSort)

    • 資料物件 :陣列、鏈結串列
    • 穩定性 : 陣列()、鏈結串列()
    • 時間複雜度 :
      • 平均 :
        • 陣列 :O(〖nlog〗^2 n)
        • 鏈結串列 : O(nlogn)
      • 額外空間複雜度 :
        • 陣列 :O(1)
        • 鏈結串列 :
          • O(1)
          • O(n)+ O(logn) ->如果非從上到下
    • 運作方式 :
      • 遞迴法（Top-down）
        1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
        2. 設定兩個指標，最初位置分別為兩個已經排序序列的起始位置
        3. 比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置
        4. 重複步驟3直到某一指標到達序列尾
        5. 將另一序列剩下的所有元素直接複製到合併序列尾
      • 迭代法（Bottom-up）
        1. 原理如下（假設序列共有n個元素）
        2. 將序列每相鄰兩個數字進行合併操作，形成(n/2)個序列，排序後每個序列包含兩/一個元素
        3. 若此時序列數不是1個則將上述序列再次合併，形成(n/4)個序列，每個序列包含四/三個元素
        4. 重複步驟2，直到所有元素排序完畢，即序列數為1

  • 快速排序(QuickSort)

    • 資料物件 :陣列、鏈結串列
    • 穩定性 : 陣列(N)、鏈結串列(Y)
    • 時間複雜度 :
      • 平均 : O(nlogn)
      • 最壞 : O(n^2)
    • 額外空間複雜度 : O(logn)
    • 運作方式 :
      1. 挑選基準值：從數列中挑出一個元素，稱為「基準」（pivot）。
      2. 分割：重新排序數列，所有比基準值小的元素擺放在基準前面 ;所有比基準值大的元素擺在基準後面（與基準值相等的數可以到任何一邊）。在這個分割結束之後，對基準值的排序就已經完成。
      3. 迴排序子序列：利用遞迴將基準值左右的子序列排序。

好啦 !! Icebear的簡介基本上就到這裡了，明天就要開始MySQL的學習了 !!