> # 相關排序 | 排序算法 | 最壞情況時間復雜度 | 平均情況時間復雜度 | 最好情況時間復雜度 | 空間復雜度 | 穩定性 | | --- | --- | --- | --- | --- | --- | | 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 穩定 | | 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩定 | | 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 穩定 | | 快速排序 | O(n^2) | O(nlogn) | O(nlogn) | O(nlog) | 不穩定 | | 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩定 | | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩定 | | 計數排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 穩定 | | 桶排序 | O(n^2) | O(n + k) | O(n + k) | O(n + k) | 穩定 | | 基數排序 | O(n \* k) | O(n \* k) | O(n \* k) | O(n + k) | 穩定 | - O(n^2) > O(n * k) > O(nlogn) > O(n + k) > O(n) > O(k) > O(1) 1. **最壞情況時間復雜度**：這是指在給定算法的所有可能輸入中，所需執行步驟的最大數量。最壞情況時間復雜度給出了算法在最不利情況下的性能。例如，對于快速排序，最壞情況時間復雜度是O(n^2)，這發生在每次選擇的基準元素都是最大或最小元素的情況下。 2. **平均情況時間復雜度**：這是指在給定算法的所有可能輸入中，所需執行步驟的平均數量。平均情況時間復雜度考慮了算法在各種情況下的性能，并給出了一個對算法性能的更全面的評估。例如，對于快速排序，平均情況時間復雜度是O(nlogn)，這是因為在大多數情況下，分區的過程能夠將數組均勻地分割成兩部分。 3. **最好情況時間復雜度**：這是指在給定算法的所有可能輸入中，所需執行步驟的最小數量。最好情況時間復雜度描述了算法在最理想情況下的性能。例如，對于插入排序，最好情況時間復雜度是O(n)，這發生在數組已經是部分有序的情況下。 4. **空間復雜度**：這是指算法在執行時所需的額外空間或內存量。空間復雜度考慮了算法所使用的額外空間與輸入規模之間的關系。例如，對于歸并排序，空間復雜度是O(n)，因為它需要一個與原始數組大小相同的輔助數組來合并子數組。 5. **穩定性**：這是指算法在排序過程中能否保持相等元素的相對順序不變。如果排序算法能夠保持相等元素的相對順序不變，則稱該算法是穩定的；否則稱為不穩定的。例如，如果對一組學生成績按照姓名進行排序，排序后相同成績的學生應該按照他們原始的順序排列，這就需要一個穩定的排序算法。插入排序和歸并排序是穩定的排序算法，而快速排序和堆排序是不穩定的排序算法。 > 選擇 1. **數據規模**：對于小規模數據集，簡單的排序算法如冒泡排序、選擇排序、插入排序可能更適合，而對于大規模數據集，則更復雜的算法如快速排序、歸并排序、堆排序更高效。 2. **數據分布**：如果數據分布近乎有序，插入排序可能更快；如果數據分布隨機，快速排序可能更適合。 3. **內存限制**：某些排序算法需要額外的內存空間，如歸并排序的遞歸實現，而某些算法是原地排序算法，如快速排序、堆排序。 4. **穩定性**：某些情況下，需要保持相等元素的相對順序不變，這時穩定排序算法如歸并排序、計數排序更適合。 5. **時間限制**：對于需要更快排序的場景，可以考慮時間復雜度較低的算法，如快速排序、堆排序 > # 相關閱讀 [十大經典排序算法（動圖演示）](https://www.cnblogs.com/onepixel/p/7674659.html)