[Algorithm] Quick Sort (快速排序)
快速排序（英語：Quicksort），又稱分割區交換排序（partition-exchange sort），簡稱快排
Quick Sort 的定義 (參考維基百科)
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的2個子序列，然後遞迴地排序兩個子序列
主要步驟
從數列中挑選一個基準點，接著分別由數列的兩邊開始往中間找
如果右邊找到一個值比基準點小，左邊找到一個值比基準點大，就將他們互換
如此將所有數列跑過一輪即可完成排序
用文字描述起來比較抽象 XD，有點類似二元分類的概念，可以參考維基上的動圖比較好懂
時間複雜度 O(nlogn)
以下實作皆為 in-place 版本 (即不建立新 array，直接操作原 array)
範例程式碼
Ruby 範例
附上 Ruby 的 online sandbox，有興趣可以把 code 貼進去玩玩看
arr = [9, 4, 2, 3, 5, 7, 8, 1, 6]
def quick_sort(array, first, last)
if first < last
p_index = partition(array, first, last)
quick_sort(array, first, p_index-1)
quick_sort(array, p_index+1, last)
end
return array
end
# 從 array 中選出一個 pivot 當作基準，用這個 pivot 將 array 切成兩半，使左半邊數值全都小於 pivot，右半邊數值全都大於等於 pivot
def partition(array, first, last)
pivot = array[last]
dividing_index = first
(first...last).each do |index|
value = array[index]
# 如發現小於等於 pivot 的值時，就跟大於 pivot 的值交換位置
if value <= pivot
array[index] = array[dividing_index]
array[dividing_index] = value
dividing_index += 1
end
end
# 將 pivot 交換至 dividing_index 位置，這樣 dividing_index 左邊的值都會小於等於 pivot，右邊都會大於 pivot
array[last] = array[dividing_index]
array[dividing_index] = pivot
dividing_index
end
pp quick_sort(arr, 0, 8)
結果如下
JavaScript 範例
JavaScript 的 online sandbox，有興趣可以把 code 貼進去玩玩看
let arr = [9, 4, 2, 3, 5, 7, 8, 1, 6]
const quickSort = (array, first, last) => {
if (first < last) {
let pivotIndex = partition(array, first, last);
quickSort(array, first, pivotIndex-1);
quickSort(array, pivotIndex+1, last);
}
return array;
};
const partition = (array, first, last) => {
const pivot = array[last];
let dividing_index = first;
for (let i = first; i < last; ++i) {
if (array[i] <= pivot) {
swap(array, dividing_index, i);
dividing_index++;
}
}
swap(array, dividing_index, last);
return dividing_index;
}
const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];
console.log(quickSort(arr, 0, arr.length - 1));
結果如下
