排序法與時間複雜度

排序法比較

排序法	時間複雜度	特性	數據大小	數據初始狀態	空間複雜度	數據範圍	穩定排序
計數/基數/桶排序法	O(n)	非比較	大			有限範圍整數用計數或桶排序。非整數範圍用基數排序
快速/合併/堆排序	O(nlog2n)	分治法	大	完全隨機數據	不需額外空間用快速或堆排序。需則用合併排序	無	穩定排序用合併排序。非穩定用快速或堆排序
選擇/插入/冒泡排序	O(n2)	簡單	小	接近排好插入排序的最佳時間複雜度為O(n)		穩定排序用插入排序

特性

- 越簡單的越慢，如冒泡/選擇/插入排序，時間複雜度O(n^2)。

- 帶分治策略較複雜，如快速/合併/堆排序，時間複雜度O(nlogn)。

- 非比較靠數據特性排序更快，如計數/基數/桶排序，時間複雜度O(n+k)。

使用那種排序法判斷依據

- 數據大小

10-1000個，用時間複雜度O(n^2)的演算法。

大於1000個，用時間複雜度O(nlogn)或O(n+k)的演算法。

- 數據初始狀態

已接近排序，插入排序有效，最佳時間複雜度為O(n)。

完全隨機數據，用時間複雜度O(nlogn)的演算法。

如何判斷數據已接近排序或完全隨機，參考給定一數列，算其中有多少個逆序對

- 空間複雜度限制

原地排序，不需額外空間，用快速排序或堆排序。

需額外空間，用合併排序。

- 數據範圍與特性

範圍有限數據，如排序有限範圍整數（如0-100），用計數或桶排序。

非整數數據，如浮點數或字串，用基數排序，特別在多位數情況。

- 穩定性要求

穩定排序，用合併或插入排序。

非穩定排序，用快速或堆排序。