DIV CSS 佈局教程網

JavaScript 八大排序演算法總整理:原理、穩定性與複雜度
編輯:關於JavaScript     

資料結構與演算法是程式設計的底盤。排序更常出現在筆試與面談中,因此值得反覆溫習。排序可分為內部排序與外部排序,前者在記憶體中完成,本文只討論內部排序,涵蓋插入、選擇、交換、歸並與基數五大類共八種演算法。

1,插入排序:直接插入排序和希爾排序
2,選擇排序:簡單選擇排序和堆排序
3,交換排序:冒泡排序和快速排序
4,歸並排序
5,基數排序

直接插入排序

假設前 n-1 個數已經排好序,把第 n 個數插入到這段有序序列中的正確位置,使前 n 個數依然有序。反覆進行直到全部完成。實作上從右往左比較、邊比邊往後挪,遇到相等就停下,因此是穩定排序。

希爾排序

先取一個較大的增量 d(例如 n/2)把資料分組,組內元素的下標相差 d,各自做直接插入排序;接著縮小增量再分組排序,直到增量為 1 的最後一趟。先讓元素「大範圍地」靠近最終位置,能大幅減少後段比較次數,是第一個實用且突破 O(n²) 的排序演算法。

簡單選擇排序

每一趟從未排序區中找出最小值,與該區的第一個位置交換,然後把範圍往後縮一格,直到只剩兩個元素。比較次數固定為 n(n-1)/2,交換次數很少,但因為長距離交換會打亂相同元素的相對次序,所以不穩定。

堆排序

堆排序是樹形選擇排序,可視為對簡單選擇排序的改良。若 n 個元素的序列 (h1, h2, ..., hn) 滿足 hi ≥ h2i 且 hi ≥ h2i+1(i = 1, 2, ..., n/2),即稱為堆;此時堆頂必為最大值,也就是所謂的大頂堆。完全二叉樹能很直觀地表現堆的結構:堆頂為根,其餘為左右子樹。

做法是先把序列調整成堆,此時根節點最大;將根節點與最後一個節點交換,再對前面 n-1 個元素重新調整成堆,如此反覆直到只剩兩個節點。因此堆排序由兩個部分組成:一是建立堆的篩選(sift down)函式,二是反覆呼叫它完成排序的函式。時間複雜度穩定為 O(n log n),且只需常數額外空間,但建堆過程中的長距離搬移會破壞穩定性。

冒泡排序

在尚未排好的區間中,由頭向尾比較相鄰兩元素,若順序與需求相反就交換,讓較大的數逐步往後沉、較小的往前冒。每一趟結束後,最大值必定落在區間末端。因為只交換相鄰元素、相等時不交換,所以穩定。

快速排序

選一個基準元素(通常取頭或尾),掃描一趟把序列分成「小於基準」與「大於等於基準」兩半,此時基準已落在最終正確位置,再對兩半遞迴套用同樣手法。平均表現最佳的實用排序之一,但基準與遠端元素的長距離交換會破壞穩定性,且最壞情況(例如已排序資料配上固定取頭的基準)會退化到 O(n²)。

歸並排序

把待排序序列分成若干子序列,每個子序列各自有序,再將有序子序列兩兩合併成更大的有序序列,最終合成整體有序。時間複雜度穩定為 O(n log n)、且穩定,代價是需要 O(n) 的額外陣列。

基數排序

把所有待比較的數值(正整數)補前導零統一為相同位數,再從最低位開始逐位排序,每一輪都以前一輪的結果為基礎。等最高位也排完,整個序列自然有序。這是一種「分配—收集」式的排序,適合位數有限而元素龐大的情況,例如大量固定格式的編號。

穩定性逐一檢視

(1)直接插入排序:比較從有序段末端開始,遇到相等元素會停下並插入其後,相對次序不變,穩定。

(2)希爾排序:單趟插入排序本身穩定,但不同增量分組時,相同元素可能在不同組中各自移動,最終相對次序被打亂,不穩定。

(3)簡單選擇排序:例如 8 5 8 4 1 0,第一趟會拿第 1 個 8 與 0 交換,原本兩個 8 的前後關係就此改變,不穩定。

(4)堆排序:篩選時父節點與子節點之間的長距離交換,可能讓相同元素跨越彼此,不穩定。

(5)冒泡排序:只比較交換相鄰元素,相等即不動,穩定。

(6)快速排序:例如 6 4 4 5 4 7 8 9,基準 6 與第三個 4 交換後,前面幾個 4 的相對順序就被破壞,不穩定。

(7)歸並排序:合併時若兩側當前元素相等,優先取左側(前面序列)的元素,次序得以保留,穩定。

(8)基數排序:按位分配再依序收集,同一位數值的元素維持輸入順序,因此穩定。

總表對照

實務上的選擇

多數語言的標準庫早已內建排序,不必自己刻。但理解這些特性的意義在於知道「為什麼」:資料量小或接近有序時插入排序反而快;需要穩定排序且不能多佔空間時,選項其實很少;要求效能穩定且可接受額外記憶體,歸併排序是保守好選擇;只求平均最快又不在乎穩定性,快速排序最合適。JavaScript 的 Array.prototype.sort 在現代引擎中對數字陣列需自行提供比較函式,否則會以字串順序排序,這是最常見的誤用。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved