快速排序是對氣泡排序的一種改良。它的核心思想是「分治」:挑出一個基準值,透過一趟掃描把整個序列切成左右兩段,左段全部不大於基準、右段全部不小於基準,接著對這兩段分別重複同樣的動作,直到每段子序列只剩一個元素,整個序列自然就有序了。
以下假設待排序陣列為 A[0] … A[N-1]:
low 與 high,起始時 low = 0、high = N - 1。base = A[low]。base 的元素,把它換到左側空位。base 的元素,把它換到右側空位。low === high,此時基準值就落在它最終的正確位置上。要特別注意的是:快速排序不是穩定排序。值相同的元素在過程中被長距離搬移,結束後相對順序很可能改變。
function partition(elements, low, high) {
var base = elements[low]; // 以區間首元素為基準
while (low < high) {
// 從後往前,跳過所有大於等於基準的元素
while (low < high && elements[high] >= base) high--;
elements[low] = elements[high]; // 把較小的值填進左邊空位
// 從前往後,跳過所有小於等於基準的元素
while (low < high && elements[low] <= base) low++;
elements[high] = elements[low]; // 把較大的值填進右邊空位
}
elements[low] = base; // 基準值歸位
return low; // 回傳分割點
}
function sort(elements, low, high) {
if (low >= high) return;
var pos = partition(elements, low, high);
sort(elements, low, pos - 1); // 遞迴排序左段
sort(elements, pos + 1, high); // 遞迴排序右段
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements, 0, elements.length - 1);
console.log('after : ' + elements);
這裡順手修掉了一個常見的抄寫錯誤:遞迴左段時必須傳入 low,而不是硬寫 0。寫成 0 在第一次呼叫時剛好沒差,但只要 sort 被巢狀呼叫過就會出錯。