[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 |