一谈，原始的快速排序
function swap(arr, i, j) { let temp = arr[i] arr[i] = arr[j] arr[j] = temp}function quickSort(arr, fromIndex, length) { if (length < 2) { return } // arr[midIndex] 的位置已经固定，不用在排 let midIndex = partition(arr, fromIndex, length) let subLength = midIndex - fromIndex quickSort(arr, fromIndex, subLength) if (midIndex + 1 !== arr.length) { quickSort(arr, midIndex + 1, length - subLength - 1) }}function partition(arr, fromIndex, length) { let lastIndex = fromIndex + length - 1 let pivot = arr[lastIndex] let lastIndexUnderPivot = fromIndex - 1 for (let currentIndex = fromIndex; currentIndex < lastIndex; currentIndex++) { if (arr[currentIndex] <= pivot) { swap(arr, lastIndexUnderPivot + 1, currentIndex) lastIndexUnderPivot++ } } swap(arr, lastIndexUnderPivot + 1, lastIndex) return lastIndexUnderPivot + 1}let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10, 312, 312, 1, 1, 2323, 4, 56, 3, 14, 5543]quickSort(arr, 0, arr.length)console.log(arr) // [ 1, 1, 1, 1, 2, 3, 3, 4, 5, 6, 7, 10, 11, 14, 17, 56, 312, 312, 2323, 5543 ] 二谈，优化后的快速排序
适时的采用插入排序
代码略
随机化快速排序
改变选择主元 pivot 的方式，从选择末尾的元素，改为随机选择
修改 partition 函数
function partition(arr, fromIndex, length) { let lastIndex = fromIndex + length - 1 let randomIndex = fromIndex + Math.floor(Math.random() * length) // 随机索引 swap(arr, randomIndex, lastIndex) // 与最后一个元素交换，其余不变 let pivot = arr[lastIndex] let lastIndexUnderPivot = fromIndex - 1 for (let currentIndex = fromIndex; currentIndex < lastIndex; currentIndex++) { if (arr[currentIndex] <= pivot) { swap(arr, lastIndexUnderPivot + 1, currentIndex) lastIndexUnderPivot++ } } swap(arr, lastIndexUnderPivot + 1, lastIndex) return lastIndexUnderPivot + 1} 三路快排
function swap(arr, i, j) { let temp = arr[i] arr[i] = arr[j] arr[j] = temp}function quickSort(arr, fromIndex, length) { if (length < 2) { return } let [firstIndexEqualPivot, lastIndexEqualPivot] = partition(arr, fromIndex, length) // pivot 都已经排好序 quickSort(arr, fromIndex, firstIndexEqualPivot - fromIndex) let subLength = fromIndex + length - 1 - (lastIndexEqualPivot + 1) + 1 // subLength = 末尾索引 - 第一个大于主元素的索引 + 1 quickSort(arr, lastIndexEqualPivot + 1, subLength)}function partition(arr, fromIndex, length) { let lastIndex = fromIndex + length - 1 let randomIndex = fromIndex + Math.floor(Math.random() * length) swap(arr, randomIndex, lastIndex) let pivot = arr[lastIndex] let lastIndexUnderPivot = fromIndex - 1 let firstIndexOverPivot = lastIndex let currentLeftIndex = fromIndex let currentRightIndex = lastIndex - 1 while (currentLeftIndex <= currentRightIndex) { while (arr[currentLeftIndex] <= pivot) { if (arr[currentLeftIndex] < pivot) { swap(arr, lastIndexUnderPivot + 1, currentLeftIndex) lastIndexUnderPivot++ } currentLeftIndex++ } while (arr[currentRightIndex] >= pivot) { if (arr[currentRightIndex] > pivot) { swap(arr, firstIndexOverPivot - 1, currentRightIndex) firstIndexOverPivot-- } currentRightIndex-- } // 越界 if (currentLeftIndex > lastIndex - 1) { break } // 越界 if (currentRightIndex < fromIndex) { break } // 越界 if (currentLeftIndex > currentRightIndex) { break } // 此时arr[currentLeftIndex] > pivot, arr[currentRightIndex] < pivot swap(arr, currentLeftIndex, currentRightIndex) } swap(arr, firstIndexOverPivot, lastIndex) let firstIndexEqualPivot = lastIndexUnderPivot + 1 let lastIndexEqualPivot = firstIndexOverPivot return [firstIndexEqualPivot, lastIndexEqualPivot]}let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10]quickSort(arr, 0, arr.length)console.log(arr) // [ 1, 2, 3, 5, 6, 1, 7, 10, 11, 17 ] 尾递归
套路和中的一样，将要用但是来不及用的参数存起来，在合适的时候，再用，这里的合适一般都是计算至叶结点的时候
仅需修改 quickSort 函数如下，传入参数时，多个空数组
function quickSort(arr, fromIndex, length, argsArr) { if (length < 2) { if (argsArr.length === 0) { return } let args = argsArr.pop() return quickSort(arr, args[0], args[1], argsArr) } let [firstIndexEqualPivot, lastIndexEqualPivot] = partition(arr, fromIndex, length) // pivot 都已经排好序 argsArr.push([lastIndexEqualPivot + 1, fromIndex + length - 1 - (lastIndexEqualPivot + 1) + 1]) return quickSort(arr, fromIndex, firstIndexEqualPivot - fromIndex, argsArr)}...let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10]quickSort(arr, 0, arr.length, [])console.log(arr) // [ 1, 2, 3, 5, 6, 1, 7, 10, 11, 17 ] 四谈，快速排序的应用，top-k 问题
《算法导论》9.3 最坏情况为线性时间的选择算法
输入是n个不同元素组成的数组，求第i小的元素，i从0算起
function insertSort(arr, fromIndex, length) { for (let currentIndex = fromIndex + 1; currentIndex < fromIndex + length; currentIndex++) { let currentCard = arr[currentIndex] let j = currentIndex - 1 for (j; j >= fromIndex; j--) { if (currentCard > arr[j]) { break } else { arr[j + 1] = arr[j] } } arr[j + 1] = currentCard }}// 确定n个不同元素的数组中，第i小的元素function BFPRT(arr, flag) { if (arr.length === 1) { return arr[0] } let medianArr = [] for (let i = 0; i < arr.length; i = i + 5) { if (i + 5 > arr.length) { insertSort(arr, i, arr.length - i) if ((arr.length - i) % 2 === 0) { let index = (arr.length - i) / 2 + i - 1 medianArr.push(arr[index]) } else { let index = Math.floor((arr.length - i) / 2) + i medianArr.push(arr[index]) } } else { insertSort(arr, i, 5) medianArr.push(arr[i + 2]) } // 对每组元素进行插入排序，确定中位数 } let subFlag = 0 if (medianArr.length % 2 === 0) { subFlag = medianArr.length / 2 - 1 } else { subFlag = Math.floor(medianArr.length / 2) } let pivot = BFPRT(medianArr, subFlag) let [leftArr, rightArr] = partition(arr, pivot) if (leftArr.length === flag) { return pivot } if (leftArr.length > flag) { return BFPRT(leftArr, flag) } if (leftArr.length < flag) { return BFPRT(rightArr, flag - leftArr.length - 1) }}function partition(arr, pivot) { let leftArr = [] let rightArr = [] for (let i = 0; i < arr.length; i++) { if (arr[i] < pivot) { leftArr.push(arr[i]) } if (arr[i] > pivot) { rightArr.push(arr[i]) } } return [leftArr, rightArr]}let arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 11, 13]console.log(BFPRT(arr, 2))