Basics Sorting - 基礎排序演算法

演算法複習——排序

演算法分析

  1. 時間複雜度-執行時間(比較和交換次數)
  2. 空間複雜度-所消耗的額外記憶體空間
    • 使用小堆疊、隊列或表
    • 使用鏈表或指針、數組索引來代表數據
    • 排序數據的副本

在OJ上做題時,一些經驗法則(rule of thumb)以及封底估算(back-of-the-envelop calculation)可以幫助選擇適合的演算法,一個簡單的經驗法則是

10^9 operations per second

舉例來說,如果今天遇到一個題目,時間限制是1s,但僅有10310^3筆輸入數據,此時即使使用O(n2)O(n^2)的演算法也沒問題,但若有10510^5筆輸入,則O(n2)O(n^2)的演算法則非常可能超時,在實作前就要先思考是不是有O(nlogn)O(n\log n)或更快的演算法。

對具有重鍵的數據(同一組數按不同鍵多次排序)進行排序時,需要考慮排序方法的穩定性,在非穩定性排序演算法中需要穩定性時可考慮加入小索引。

穩定性:如果排序後文件中擁有相同鍵的項的相對位置不變,這種排序方式是穩定的。

常見的排序演算法根據是否需要比較可以分為如下幾類:

  • Comparison Sorting
    1. Bubble Sort
    2. Selection Sort
    3. Insertion Sort
    4. Shell Sort
    5. Merge Sort
    6. Quck Sort
    7. Heap Sort
  • Bucket Sort
  • Counting Sort
  • Radix Sort

從穩定性角度考慮可分為如下兩類:

  • 穩定
  • 非穩定

Reference

results matching ""

    powered by

    No results matching ""