[TOC] # 描述 快排是處理大數據最快的排序算法之一。它是一種分而治之的算法，通過遞歸的方式將數據依次分解為包含較小元素和較大元素的不同子序列。該算法不斷重復這個步驟直至所有數據都是有序的。 <br> <br> # 動圖演示  <br> <br> # 實現 1. 選擇一個基準元素，將列表分割成兩個子序列； 2. 對列表重新排序，將所有小于基準值的元素放在基準值前面，所有大于基準值的元素放在基準值的后面； 3. 分別對較小元素的子序列和較大元素的子序列重復步驟1和2 ~~~ function quickSort(arr) { // 遞歸出口 if (arr.length < 2) return arr const left = [] const right = [] const pivotValue = arr[0] // 中心點 for (let i = 1; i < arr.length; i++) { if (arr[i] < pivotValue) { left.push(arr[i]) } else { right.push(arr[i]) } } // quickSort(left).concat(pivotValue,quickSort(right)) return [...quickSort(left), pivotValue, ...quickSort(right)] } ~~~ <br> <br> # 原地快速排序 ~~~ function QuickSortInPlace(originalArray, inputLowIndex = 0, inputHighIndex = originalArray.length - 1) { const array = originalArray const partitionArray = (lowIndex, highIndex) => { const swap = (leftIndex, rightIndex) => { const temp = array[leftIndex]; array[leftIndex] = array[rightIndex]; array[rightIndex] = temp; }; const pivot = array[highIndex]; let partitionIndex = lowIndex; for (let currentIndex = lowIndex; currentIndex < highIndex; currentIndex += 1) { if (array[currentIndex] < pivot) { swap(partitionIndex, currentIndex); partitionIndex += 1; } } swap(partitionIndex, highIndex); return partitionIndex; }; if (inputLowIndex < inputHighIndex) { const partitionIndex = partitionArray(inputLowIndex, inputHighIndex); QuickSortInPlace(array, inputLowIndex, partitionIndex - 1); QuickSortInPlace(array, partitionIndex + 1, inputHighIndex); } return array; } ~~~ # 復雜度 | 最好 | 平均| 最差| 空間復雜度| 穩定性| | :-: | :-: | :-: | :-: | :-: | :-- | | n?log(n) | n?log(n) | n2 | log(n) | No |