⚡ 快速排序法演示

操作原理

  1. 選一個基準值（pivot），把陣列分成小於與大於 pivot 的兩側。
  2. pivot 排到最終正確位置後，左右兩側可獨立排序。
  3. 對左子陣列、右子陣列重複同樣分割。
  4. 遞迴結束後，整體陣列即完成排序。

操作過程步驟

  1. 呼叫 quickSort(low, high)。
  2. 若 low >= high，該區間已完成。
  3. 執行 partition：以最右元素作為 pivot。
  4. 掃描 low..high-1，把小於等於 pivot 的元素移到左側。
  5. 最後把 pivot 交換到分界位置 p。
  6. 遞迴排序 [low..p-1] 與 [p+1..high]。

時間複雜度分析

最壞情況：O(n^2)
每次分割都非常不平均（例如已排序資料且 pivot 取邊界）
平均情況：O(n log n)
隨機資料下，分割通常較平均，效率很好
最佳情況：O(n log n)
每次都能接近對半分割
空間複雜度：O(log n)
主要來自遞迴呼叫堆疊（平均）

視覺化演示

按下「開始排序」觀察 pivot 分割與遞迴排序流程
目前分割區間
pivot
比較中
交換中
排序完成
比較次數: 0
交換次數: 0