本文同步更新於個人網站中,有更好的排版和程式碼區塊 highlighting 支援。
快速排序法(Quick Sort)是對氣泡排序法的一種改進,是一個基於分治法(Divide and Conquer)的排序演算法。它不像 merge sort 那樣一上來就將陣列切成“碎片”,而是逐漸對要處理的陣列進行切割,每次切成兩部分,讓其左邊都小於某個數,右邊都大於某個數,然後再對左右兩邊進行同樣的操作(快速排序),直到每個子陣列長度為 1,原陣列就會變成有序的了。
從下面這段程式碼來具體理解一下,它的基本架構如下:
function quickSort (array) {
function QuickSort(array, left, right) {
if (left < right) {
let index = partition(array, left, right);
QuickSort(array, left, index - 1);
QuickSort(array, index + 1, right);
}
}
QuickSort(array, 0, array.length - 1);
return array;
}
function partition(array, left, right) { // D&C function
// TODO
}
quickSort
是一個進入點,它會呼叫遞迴函式 QuickSort
。QuickSort
內部有一個 partition
輔助函式,它會選中某個元素作為基準值(pivot,分界值),實作對子陣列的左右切割,保證左邊的元素都比 pivot 小,右邊的元素都比 pivot 大,最後回傳 pivot 的索引值,方便再對左右兩陣列呼叫 QuickSort
。
對於 quick sort 的 partition
函式的實作,通常有以下 3 種。
使用左右指標法實作 partition
方法的步驟如下:
當 left >= right
時,一趟 quick sort 就完成了,這時將 pivot 和 array[left]
的值進行一次交換:
function partition(array, left, right) {
const pivot = array[right];
let pivotIndex = right;
while (left < right) {
while (left < right && array[left] <= pivot) {
// 1. 防止越界需要 left < right
// 2. array[left] <= pivot 因為可能存在相同元素
left++; // 找到比 pivot 大的數
}
while (left < right && array[right] >= pivot) {
right--; // 找到比 pivot 小的數
}
swap(array, left, right);
}
// 最後一個比 pivot 大的 left 元素要與 pivot 交換
swap(array, left, pivotIndex);
return left; // 回傳的是中間的位置
}
上面程式碼的執行過程可以參考這張圖:
使用挖坑法實作 partition
方法的步驟如下:
array[left]
。array[right]
。挖坑法的程式碼實作如下:
function partition(array, left, right) {
const pivot = array[right]; // 坑位為 array[right]
while (left < right) {
while (left < right && array[left] <= pivot) {
left++;
}
array[right] = array[left]; // 坑位變成 array[left]
while (left < right && array[right] >= pivot) {
right--;
}
array[left] = array[right]; // 坑位變成 array[right]
}
array[right] = pivot;
return left;
}
坑位在程式碼上的變化如下:
array[left] -> array[right] -> array[left] -> array[right] -> ...
這是填坑的示意圖:
挖坑法比左右指標法好理解,並且不依賴額外的 swap
函式,具體執行過程可以參考下面這張圖:
使用前後指標法實作 partition
方法的步驟如下:
定義兩個指標,一前一後,前面的指標尋找比 pivot 小的元素,後面的指標尋找比 pivot 大的元素。前面的指標找到符合條件的元素後,將前後指標所指向的元素交換位置,當前面的指標遍歷完整個陣列時,將 pivot 與後指標的後一位交換位置,然後回傳後指標的位置。
function partition(array, left, right) {
const pivot = array[right];
let curr = left; // 找比 pivot 大的數
let prev = curr - 1; // 找比 pivot 小的數
while (curr <= right) {
if (array[curr] <= pivot && ++prev !== curr) {
swap(array, prev, curr);
}
curr++;
}
return prev;
}
前後指標法的執行過程可以參考下面這張圖:
這個方法最大的優勢是支援對鏈結串列(Linked List)進行排序,而左右指標法和挖坑法只能針對陣列進行排序。
Quick Sort 的最佳化主要涉及到三個方面:
A[0]
中,像在前文中使用 swap
方法時一樣,我們只需要做交換的工作,最終 A[i]
與 A[j]
融合,再將 A[0]
位置的數值賦值回 A[i]
。因為沒有了多次交換的操作,所以效率會有所提升。待排序序列長度 N = 10,在 5 和 20 之間任一截止範圍都有可能產生類似效果。下面是小陣列使用 insertion sort 的程式碼:
if (high - low + 1 < 10) {
insertionSort(array, low, high);
return;
} else {
quickSort(array, low, high);
}
完整程式碼如下:
function getMid(array, left, right) {
const mid = left + Math.floor((right - left) / 2);
if (array[left] <= array[right]) {
if (array[mid] < array[left]) {
return left;
} else if (array[mid] > array[right]) {
return right;
} else {
return mid;
}
} else {
if (array[mid] < array[right]) {
return right;
} else if (array[mid] > array[left]) {
return left;
} else {
return mid;
}
}
}
// 左右指標法
function partition(array, left, right) {
const mid = getMid(array, left, right);
swap(array, mid, right); // 把 pivot 移到最右邊
const pivot = array[right];
let pivotIndex = right;
while (left < right) {
while (left < right && array[left] <= pivot) {
left++;
}
while (left < right && array[right] >= pivot) {
right--;
}
swap(array, left, right);
}
swap(array, left, pivotIndex);
return left;
}
// 挖坑法(前後指標法同理)
function partition(array, left, right) {
const mid = getMid(array, left, right);
swap(array, mid, right); // 把 pivot 移到最右邊
const pivot = array[right];
while (left < right) {
while (left < right && array[left] <= pivot) {
left++;
}
array[right] = array[left];
while (left < right && array[right] >= pivot) {
right--;
}
array[left] = array[right];
}
array[right] = pivot;
return left;
}
遞迴主要是在劃分子區間,如果要用非遞迴的方式實作 quick sort,可以使用一個 stack 來存放區間即可。
要將遞迴程式改造成非遞迴程式,首先想到的就是使用 stack,因為遞迴的本質就是一個 push 元素到 stack 的過程。下面是一個使用 stack 的非遞迴實作方式:
function quickSortStack(array, start, end) {
const stack = [];
stack.push(end);
stack.push(start);
while (stack.length) {
const left = stack.pop();
const right = stack.pop();
const index = partition(array, left, right);
if (left < index - 1) {
stack.push(index - 1);
stack.push(left);
}
if (right > index + 1) {
stack.push(right);
stack.push(index + 1);
}
}
}
給你一個由整數組成的陣列,請找出其中最小的 K
個數。例如,給你的陣列是 [11, 9, 6, 17, 0, 1, 2, 18, 3, 4, 8, 5]
和 K = 4
,那麼最小的 4 個數是 [0, 1, 2, 3]
。
思路:TopK 問題也可以利用在實作 quick sort 時用到的 quick select 演算法來解決,我們知道 partition
函式會回傳一個 pivot,pivot 左邊的元素都比 pivot 小,右邊的元素都比 pivot 大。我們可以一直去呼叫 partition
函式,直到 pivot 的位置剛好是 K - 1
,那麼 pivot 左邊的元素就是最小的 K
個數。
我們打開 day21-quick-sort/getTopK.js
來實作看看:
function getTopK(array, k) {
if (array.length >= k) {
let low = 0;
let high = array.length - 1;
let pivot = partition(array, low, high);
// 不斷調整分治的範圍,直到 pivot 的 index 等於 k - 1
while (pivot !== k - 1) {
// 大了,往左(前)邊調整
if (pivot > k - 1) {
high = pivot - 1;
pivot = partition(array, low, high);
}
// 小了,往右(後)邊調整
if (pivot < k - 1) {
low = pivot + 1;
pivot = partition(array, low, high);
}
}
return array.slice(0, k);
}
}
Name | Average | Best | Worst | Space | Method | Stable |
---|---|---|---|---|---|---|
Quick sort | In-place | No |