快速排序

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search

快速排序quicksort)係一種用嚟將一個數列入面啲數字由細至大排好嘅演算法。步驟如下[1][2]

  1. 喺個數列入面是但揀一個數字,設佢做基準(pivot)。
  2. 重新排序數列:將個數字重新排過,令到數值上細過個基準嘅數字冚唪唥都搬去個基準前面,而數值上大過個基準嘅數字就要冚唪唥喺嗮個基準後面;做咗呢個步驟之後,個基準會喺正佢嘅最終位置。
  3. 將個數列分做兩橛-「細過個基準嗰柞數字」同埋「大過個基準嗰柞數字」,並且分別噉對嗰兩橛做上述嗰兩個步驟。

呢個演算法俾人好廣泛噉攞嚟將啲數字列嘅次序排好(一個整齊噉排好咗嘅數列可以攞嚟做第啲緊要嘅作業)。

參考[編輯]

  1. Sedgewick, R. (1978). "Implementing Quicksort programs". Comm. ACM. 21 (10): 847–857.
  2. Dean, B. C. (2006). "A simple expected running time analysis for randomized "divide and conquer" algorithms". Discrete Applied Mathematics. 154: 1–5.