排序演算法賽跑

最多六種排序法跑同一排亂序長條，比的是操作次數，不是秒數。看氣泡排序慢慢爬。

時鐘 0 次操作

數字都是真的：每一次比較、每一次寫入都會照實重播。全部在你的瀏覽器裡執行。一開始賽道上是四種，選擇排序和堆積排序在上方的按鈕列裡點一下就能加入。先點一下賽道或任一按鈕，鍵盤才會生效：空白鍵開始、暫停、繼續，→ 前進一個操作。

關於這場賽跑

為什麼公平。每條跑道拿到的陣列完全一樣：場次號碼、長條數、排列方式都相同。每一拍，還沒跑完的跑道都會重播同樣數量的真實操作，所以名次就是總操作數的高低。跑道上方的時鐘算的是操作次數，不是秒數，因為用 JavaScript 計時，量到的是你的瀏覽器，不是演算法。

什麼算一次操作。兩個元素比一次大小，或往陣列寫入一次，就算一次操作。交換等於寫兩次。合併排序會先把值複製到另一塊緩衝區，這些複製不算，但每個寫回陣列的值都算，就算它落回原本的位置也一樣。插入排序會先把要插入的值拿在手上，跟它比較算一次比較，放回去只有真的移動過才算一次寫入。打亂本身不計。

為什麼「慢」的排序也會贏。Big-O 講的是資料變多時工作量怎麼成長，不代表每一副牌都是這樣。這個氣泡排序實作只要有一趟沒交換就會提早結束，所以排好的資料只要 n − 1 次比較、零次寫入（64 根就是 63 次操作，和插入排序並列第一，選「已排序」就看得到）；插入排序遇到每根長條都快到定位時，也幾乎不用做事。這裡的「幾乎排好」是：長條一開始依序排好，再把 max(1, n/10) 對相鄰的長條互換，所以最多只有 n/10 對順序是錯的，也沒有任何一根離定位超過 n/10 格。在這種資料上，我們試過的每一場（種子 1 到 200、16 到 256 根），插入排序都贏過另外五種，比較次數只比 n 多一點。隨機長條上，n² 的演算法一次都沒贏過。試試「幾乎排好」，再試「反向」。

為什麼這個快速排序實作會變慢。它拿最後一個元素當基準（Lomuto 分割法）。遇到已排序或反向的資料，每次分割都只切掉一個元素，比較次數剛好是 n(n − 1)/2，64 根長條就是 2,016 次，跟選擇排序一樣多。「只有幾種值」也會拖慢它，但沒那麼嚴重：值只有五種，一長串相同的長條會切得很歪，128 根時快速排序的比較次數是合併排序的 2.5 到 3.4 倍（種子 1 到 200）。實際的函式庫會把基準挑得更仔細，或在分割失衡時換演算法。

Big-O 一覽，以及這場賽跑沒量的東西。

演算法	工作量
氣泡排序	O(n²)；有提早結束的設計，最好情況 O(n)
插入排序	O(n²)；最好情況 O(n)
選擇排序	一律 O(n²)，比較次數剛好是 n(n − 1)/2
合併排序	一律 O(n log n)
快速排序	平均 O(n log n)，最壞 O(n²)
堆積排序	O(n log n)

這場賽跑不量實際花的時間、快取的影響，也不量記憶體。實務上的排序大多是混合式：V8 的 Array.prototype.sort 用 TimSort，C++ 的 std::sort 通常是 introsort。

快速導覽

使用情境、常見問題與相關工具

把需要的說明放在工具下方，讓第一次使用與之後回來複用都更順。

英文搜尋: sorting algorithm race、which sorting algorithm is fastest、bubble sort vs quicksort side by side、sorting algorithms compared visually、merge sort vs quick sort race

使用方式

先完成一次順手的操作

預設四種上場，點「選擇排序」或「堆積排序」就能加入，點已選的就是拿掉（至少留兩種）。再選資料排法（隨機、幾乎排好、已排序、反向、只有幾種值）和長條數量。每次更動、每次重新打亂，新的一場馬上開跑；「重置」才會回到起跑線，等你按「開始賽跑」。
每條跑道排的都是同一副長條。可以暫停、「單步」一次走一個操作，或按「直接跑完」跳到終點；跑道一衝線，計分板就把成績鎖上去，再用一行字告訴你誰贏、贏多少。
按「再賽一場」會重新打亂；複製連結的話，任何人打開都會看到完全一樣的一場。

常見情境

這個工具實際適合拿來做什麼

64 根隨機長條：氣泡排序對上快速排序保持預設，直接看第 2026 場。快速排序 625 次操作最先到，合併排序 687 次緊跟著，這時氣泡排序（4,099）和插入排序（2,255）才排到一半；每條跑道底下的細條就是排好的進度。
插入排序的主場：幾乎排好的資料選「幾乎排好」、128 根，讓六種全部上場。這裡的幾乎排好，是只有少數相鄰長條對調（127 對相鄰的長條裡最多 12 對順序錯了），所以插入排序只要比 128 多一點的比較次數，選擇排序卻永遠剛好 8,128 次。我們試過的每一場（種子 1 到 200），插入排序都最先到，128 根時是 145 到 163 次操作。
已排序：氣泡和插入並列 63 次選「已排序」、64 根，讓六種全部上場。氣泡排序提早結束的設計和插入排序，都只要 63 次操作（63 次比較、零次寫入），並列第一；合併排序要 576 次操作，快速排序和選擇排序各要 2,016 次比較。
反向陣列：合併排序獲勝，氣泡排序要 6,048 次選「反向」、64 根，讓氣泡、插入、選擇、合併、快速上場。合併排序 576 次操作就跑完；氣泡排序要 6,048 次，是冠軍的 10.5 倍；這個快速排序實作拿最後一個元素當基準，要做 2,016 次比較。
只有幾種值，快速排序會被絆倒選「只有幾種值」、128 根，讓合併排序對上快速排序。值只有五種，資料裡一大堆連續相同的數字，拿最後一個元素當基準會切得很歪，快速排序的比較次數是合併排序的 2.5 到 3.4 倍（種子 1 到 200）；第 2026 場是 1,899 次對 681 次。
教學模式：六條跑道、慢速、一次一個操作六種演算法全選、32 根、慢速（每秒 60 次操作）。以這些設定來說，第 2026 場（直接開網址時的場次）大約四秒後蓋下第一個印章，是快速排序跑完它的 227 次操作；這時按暫停，再按「單步」，讓學生看合併排序和還在跑的幾條，一次比較、一次寫入長什麼樣子（畫面上有顏色說明，每條跑道也會寫出最後一個操作），最後按「直接跑完」。

常見問題

先把常見疑問說清楚

哪個排序演算法最快？

隨機資料上，O(n log n) 的合併、快速、堆積排序，工作量比 O(n²) 的氣泡、插入、選擇排序少，而且長條越多差距越大：種子 1 到 200 的結果裡，O(n²) 三種中最好的那個，64 根時至少是 O(n log n) 三種中最慢那個的 1.4 倍，128 根時至少 2.2 倍，256 根時至少 4.2 倍。在這場 64 根隨機長條的賽跑裡，合併和快速衝線時，氣泡還剩幾千次操作。不過沒有哪種演算法對每種資料都最快：資料幾乎排好時，插入排序贏過全部。

為什麼氣泡排序有時候會贏？

這個氣泡排序實作只要有一趟沒交換就會提早結束，所以排好的資料只要 n − 1 次比較、零次寫入：64 根長條就是 63 次操作，和插入排序並列第一（選「已排序」就看得到並列）。Big-O 講的是資料變多時工作量怎麼成長，不代表每一副牌都是這樣。

為什麼這裡的快速排序遇到排好或反向的資料會變慢？

這個快速排序實作拿最後一個元素當基準（Lomuto 分割法）。遇到排好或反向的資料，每次分割都只切掉一個元素，會做剛好 n(n−1)/2 次比較：64 根長條是 2,016 次，和選擇排序一樣多。實際的函式庫會把基準挑得更仔細，或換別的策略來避開。

這場賽跑公平嗎？

公平。每條跑道從同一副打亂過的陣列出發，每一拍，還沒跑完的跑道都重播同樣數量的真實操作。所以名次就是總操作數的高低，計數器顯示的是每個演算法真的做了幾次比較和寫入。

什麼算一次操作？

兩個元素比一次大小，或往陣列寫入一次，就算一次操作。一次交換算兩次寫入。合併排序會先把值複製到另一塊緩衝區，這些複製不算，但每個寫回陣列的值都算。