js如何实现数组快速排序 3种快速排序算法实现方案分享
最新回答
生生漫
2026-05-12 23:34:49
快速排序是一种基于“分而治之”策略的高效排序算法，其核心是选定一个基准值，将数组分为两部分，使左边元素小于基准值，右边元素大于基准值，然后递归地对左右子数组排序。以下是三种常见的JavaScript快速排序实现方案：
Lomuto 分区方案选择数组最后一个元素作为基准值，使用指针 i 跟踪小于基准值的元素边界。
function quickSortLomuto(arr, low, high) { if (low < high) { let partitionIndex = partitionLomuto(arr, low, high); quickSortLomuto(arr, low, partitionIndex - 1); quickSortLomuto(arr, partitionIndex + 1, high); } return arr;}function partitionLomuto(arr, low, high) { let pivot = arr[high]; let i = low - 1; for (let j = low; j <= high - 1; j++) { if (arr[j] <= pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1;}function swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}// 示例let arr = [10, 7, 8, 9, 1, 5];let n = arr.length;quickSortLomuto(arr, 0, n - 1);console.log("排序后的数组: " + arr);- 优点：实现简单直观，易于理解。
- 缺点：在数组部分有序时性能下降，因固定选择最后一个元素作为基准值可能导致分区不平衡。
Hoare 分区方案使用双指针从两端向中间扫描并交换元素，效率更高，尤其适用于已部分排序的数据。
function quickSortHoare(arr, low, high) { if (low < high) { let partitionIndex = partitionHoare(arr, low, high); quickSortHoare(arr, low, partitionIndex); quickSortHoare(arr, partitionIndex + 1, high); } return arr;}function partitionHoare(arr, low, high) { let pivot = arr[low]; let i = low - 1; let j = high + 1; while (true) { do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i >= j) { return j; } swap(arr, i, j); }}function swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}// 示例let arr = [10, 7, 8, 9, 1, 5];let n = arr.length;quickSortHoare(arr, 0, n - 1);console.log("排序后的数组: " + arr);- 优点：效率更高，尤其适合处理部分有序数组。
- 缺点：代码逻辑较复杂，递归调用时右侧子数组范围为 partitionIndex + 1, high，需注意与 Lomuto 方案的区别。
随机化快速排序在每次分区时随机选择基准值，避免最坏情况，提升平均性能。
function quickSortRandomized(arr, low, high) { if (low < high) { let partitionIndex = randomizedPartition(arr, low, high); quickSortRandomized(arr, low, partitionIndex - 1); quickSortRandomized(arr, partitionIndex + 1, high); } return arr;}function randomizedPartition(arr, low, high) { let randomIndex = Math.floor(Math.random() * (high - low + 1)) + low; swap(arr, randomIndex, high); return partitionLomuto(arr, low, high);}function swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}// 示例let arr = [10, 7, 8, 9, 1, 5];let n = arr.length;quickSortRandomized(arr, 0, n - 1);console.log("排序后的数组: " + arr);- 优点：通过随机选择基准值，有效避免最坏情况，提升平均性能。
- 扩展性：可结合 Lomuto 或 Hoare 分区方案，此处示例使用 Lomuto 分区。
- Lomuto 分区方案：适合教学理解，但性能在部分有序数组中较差。
- Hoare 分区方案：效率更高，代码复杂度稍高，适合处理部分有序数组。
- 随机化快速排序：综合性能最优，通过随机化基准值避免最坏情况，推荐在实际应用中使用。
- 理想情况：每次分区将数组均分，递归深度为 O(log n)，空间复杂度为 O(log n)。
- 最坏情况：分区极度不平衡（如数组已有序），递归深度退化为 O(n)，空间复杂度为 O(n)。
- 优化：随机化选择基准值可显著降低最坏情况概率，使空间复杂度稳定在 O(log n)。
根据实际需求选择方案：对性能要求不高且数组随机性较好时用 Lomuto；处理部分有序数组或追求高效时用 Hoare；需要稳定平均性能时优先选择随机化快速排序。
热门标签
