常用的排序算法及對比

基本思想：
每次從待排序數組中選擇最小（或最大）的元素，將它與當前序列的起始位置交換，逐步將整個數組排序。
推導過程：
設數組長度為 n，第一次遍歷需要掃描 n 個元素找到最小值，第二次掃描 (n-1) 個元素……直到最后一個元素。
總的比較次數約為：
$(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} = O(n^2)$

對于下標 i 從 0 到 n-2：
- 在區間 [i, n-1] 內找到最小元素的下標 min_index。
- 若 min_index ≠ i，則交換元素 arr[i] 與 arr[min_index]。

基本思想：
將數組分為已排序和未排序兩部分，每次取未排序部分的第一個元素，在已排序部分中找到合適的位置插入，使已排序部分始終保持有序。
推導過程：
對于每個元素，最壞情況下需要和前面所有元素比較并移動位置。第 i 個元素可能需要 i 次比較和移動，總的操作次數約為：
$1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2} = O(n^2)$
當數組已經接近有序時，比較次數大大減少，時間復雜度可以達到 O(n)。

從數組第二個元素開始（下標 1）：
- 記當前元素為 key，從已排序部分從后向前比較，若遇到比 key 大的元素則后移。
- 插入 key 到合適的位置。

基本思想：
通過多次遍歷數組，每次比較相鄰元素，如果順序錯誤則交換，將較大（或較小）的元素逐步“冒泡”到數組的一端。
推導過程：
每次遍歷最多做 n-1 次比較，整個排序需要進行 n-1 次遍歷，所以總的比較次數約為：
$(n-1) \times (n-1) = O(n^2)$

基本思想：
利用分治法，將數組遞歸地分解為兩個子序列，分別排序后再將兩個有序子序列合并成一個整體有序序列。
推導過程：
設 T(n) 為排序 n 個元素的時間復雜度，則：
$T(n) = 2T\left(\frac{n}{2}\right) + O(n)$
根據主定理，解得 T(n) = O(n log n)。

基本思想：
利用數據中已存在的自然有序（“天然有序”的子序列或“段”），先將序列分割成若干個自然有序的段，再逐步將這些段兩兩歸并。
推導過程：
如果輸入數據已經部分有序，則自然有序的段較長，合并次數減少，最佳情況時間復雜度可接近 O(n)。
最壞情況仍然為歸并排序的情況，即當數據完全無序時，各自然段長度為 1，總共需要 O(log n) 次歸并，每次歸并時間 O(n)，故為 O(n log n)。

基本思想：
利用分治策略選擇一個“基準”（這里取第一個元素），將數組分成兩部分：左邊所有元素均小于基準，右邊所有元素均大于基準，然后對這兩部分遞歸進行排序。
推導過程：
設 T(n) 為排序 n 個元素的時間復雜度，則：

其中 k 表示劃分后左側子數組的大小。
- 平均情況： 當每次劃分較為均勻（大致各半），有 T(n) = 2T(n/2) + O(n)，解得 T(n) = O(n log n)
- 最壞情況： 當劃分極不均勻（如數組已排序，且始終選擇最小或最大元素作為基準），有 T(n) = T(n-1) + O(n)，解得 T(n) = O(n2)。

算法	時間復雜度（最壞/平均/最好）	空間復雜度	穩定性	特點與適用場景
選擇排序	O(n2) / O(n2) / O(n2)	O(1)	不穩定	實現簡單，但比較次數固定，不適合大規模數據排序
插入排序	O(n2) / O(n2) / O(n)	O(1)	穩定	對部分有序數據效果好，適用于小規模數據或在線排序
冒泡排序	O(n2) / O(n2) / O(n)（優化版）	O(1)	穩定	實現簡單，但效率低，更多用于教學演示
歸并排序	O(n log n) / O(n log n) / O(n log n)	O(n)	穩定	時間復雜度穩定，適用于大規模數據，但需要額外空間
自然合并排序	O(n log n) / O(n log n) / O(n)	O(n)	穩定	能利用已有有序序列提升效率，適合部分有序數據
快速排序	O(n2) / O(n log n) / O(n log n)	O(log n)（平均）	不穩定	平均性能優異，原地排序，適合大規模數據，但最壞情況需注意

簡單排序（選擇、插入、冒泡）：
這些算法實現簡單，但時間復雜度均為 O(n2)（在最壞或平均情況下），適合數據量較小的情況。插入排序在數據部分有序時表現較好，而冒泡排序常用作教學示例。
分治排序（歸并、快速、自然合并）：
歸并排序和快速排序均有 O(n log n) 的平均時間復雜度，其中歸并排序穩定但需要額外空間，而快速排序在原地排序方面有優勢。自然合并排序則利用了數據中已有的有序性，在實際應用中對于部分有序數據可獲得較好性能。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/76253.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/76253.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/76253.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！