排序是指以特定順序（數字或字母）排列線性表的元素。排序通常與搜尋一起配合使用。
有許多排序演算法，而迄今為止最快的演算法之一是快速排序（Quicksort）。
快速排序用分治策略對給定的列表元素進行排序。這意味著演算法將問題分解為子問題，直到子問題變得足夠簡單可以直接解決為止。
從演算法上講，這可以用遞歸或循環實現。但是對於這個問題，用遞歸法更為自然。
先看一下快速排序的工作原理：
接下來透過一個例子來理解這些步驟。假設有一個含有未排序元素 [7, -2, 4, 1, 6, 5, 0, -4, 2] 的陣列。選擇最後一個元素作為基準。陣列的分解步驟如下圖所示：
在演算法的步驟1中被選為基準的元素帶顏色。分區後，基準元素始終處於陣列中的正確位置。
黑色粗體邊框的陣列表示該特定遞歸分支結束時的樣子，最後得到的陣列只包含一個元素。
最後可以看到演算法的結果排序。
這個演算法的主幹是「分割」步驟。無論用遞歸或循環的方法，這個步驟都是一樣的。
正是因為這個特點，首先寫為數組分區的程式碼partition()：
function partition(arr, start, end){
// 以最后一个元素为基准
const pivotValue = arr[end];
let pivotIndex = start;
for (let i = start; i < end; i++) {
if (arr[i] < pivotValue) {
// 交换元素
[arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
// 移动到下一个元素
pivotIndex++;
}
}
// 把基准值放在中间
[arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]]
return pivotIndex;
};程式碼以最後一個元素為基準，用變數pivotIndex 來追蹤「中間」位置，這個位置左邊的所有元素都比pivotValue 小，而右邊的元素都比pivotValue 大。
最後一步把基準（最後一個元素）與 pivotIndex 交換。
在實作了partition() 函數之後，我們必須遞歸地解決這個問題，並應用分區邏輯以完成其餘步驟：
function quickSortRecursive(arr, start, end) {
// 终止条件
if (start >= end) {
return;
}
// 返回 pivotIndex
let index = partition(arr, start, end);
// 将相同的逻辑递归地用于左右子数组
quickSort(arr, start, index - 1);
quickSort(arr, index + 1, end);
}在這個函數中先對數組進行分區，之後再對左右兩個子數組進行分區。只要這個函數收到一個不為空或有多個元素的數組，則會重複此過程。
空數組和僅包含一個元素的陣列被視為已排序。
最後用下面的例子來測試：
array = [7, -2, 4, 1, 6, 5, 0, -4, 2] quickSortRecursive(array, 0, array.length - 1) console.log(array)
輸出：
-4,-2,0,1,2,4,5,6,7
快速排序的遞歸方法更直觀。但是用迴圈實現快速排序是一個相對常見的面試題。
與大多數的遞歸到循環的轉換方案一樣，最先想到的是用堆疊來模擬遞歸呼叫。這樣做可以重複使用一些我們熟悉的遞歸邏輯，並在循環中使用。
我們需要一種追蹤剩下的未排序子數組的方法。一種方法是簡單地把「成對」的元素保留在堆疊中，用來表示給定未排序子陣列的 start 和 end。
JavaScript 沒有明確的堆疊資料結構，但是陣列支援 push() 和 pop() 函數。但不支援 peek()函數，所以必須用 stack [stack.length-1] 手動檢查堆疊頂部。
我們將使用與遞歸方法相同的「分區」功能。看看如何寫Quicksort部分：
function quickSortIterative(arr) {
// 用push()和pop()函数创建一个将作为栈使用的数组
stack = [];
// 将整个初始数组做为“未排序的子数组”
stack.push(0);
stack.push(arr.length - 1);
// 没有显式的peek()函数
// 只要存在未排序的子数组，就重复循环
while(stack[stack.length - 1] >= 0){
// 提取顶部未排序的子数组
end = stack.pop();
start = stack.pop();
pivotIndex = partition(arr, start, end);
// 如果基准的左侧有未排序的元素，
// 则将该子数组添加到栈中，以便稍后对其进行排序
if (pivotIndex - 1 > start){
stack.push(start);
stack.push(pivotIndex - 1);
}
// 如果基准的右侧有未排序的元素，
// 则将该子数组添加到栈中，以便稍后对其进行排序
if (pivotIndex + 1 < end){
stack.push(pivotIndex + 1);
stack.push(end);
}
}
}以下是測試程式碼：
ourArray = [7, -2, 4, 1, 6, 5, 0, -4, 2] quickSortIterative(ourArray) console.log(ourArray)
#輸出：
-4,-2,0,1,2,4,5,6,7
當涉及排序演算法時，將其視覺化能幫我們直觀的了解它們是如何運作的，下面這個例子搬運自維基百科：
在圖中也把最後一個元素作為基準。給定數組分區後，遞歸遍歷左側，直到將其完全排序為止。然後對右側進行排序。
現在討論它的時間和空間複雜度。快速排序在最壞情況下的時間複雜度是 $O(n^2)$。平均時間複雜度為 $O(n\log n)$。通常，使用隨機版本的快速排序可以避免最壞的情況。
快速排序演算法的弱點是基準的選擇。每選擇一次錯誤的基準（大於或小於大多數元素的基準）都會帶來最壞的時間複雜度。重複選擇基準時，如果元素值小於或大於該元素的基準時，時間複雜度為 $O(n\log n)$。
根據經驗可以觀察到，無論採用哪一種資料基準選擇策略，快速排序的時間複雜度都傾向於具有 $O(n\log n)$ 。
快速排序不會佔用任何額外的空間（不包括為遞歸呼叫保留的空間）。這種演算法稱為in-place演算法，不需要額外的空間。
更多程式相關知識，請造訪：程式設計入門！ ！
以上是深入淺析JavaScript中的快速排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！
