快速排序是一种基于“分而治之”策略的高效排序算法，其核心是选定一个基准值，将数组分为两部分，使得左边元素小于基准值，右边元素大于基准值，然后递归地对左右子数组排序。文章介绍了三种javascript实现方案：1. lomuto分区方案选择最后一个元素为基准，通过指针i划分边界，优点简单直观但易导致分区不平衡；2. hoare分区方案使用双指针从两端向中间扫描并交换元素，效率更高，尤其适用于已部分排序的数据；3. 随机化快速排序在每次分区时随机选择基准值，避免最坏情况，提升平均性能。三者中，lomuto适合教学理解，hoare更高效但代码复杂，随机化方案通常最优。此外，快速排序空间复杂度理想为o(log n)，最坏情况下退化为o(n)，随机化可有效改善此问题。
快速排序，简单来说，就是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
解决方案
快速排序的核心在于“分而治之”，选定一个基准值，将数组分成两部分，小于基准值的放左边，大于基准值的放右边，然后递归地对左右两部分进行排序。下面分享三种常见的JavaScript快速排序实现方案。
副标题1： 经典快速排序（Lomuto 分区方案）
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); // Index of smaller element
for (let j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
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);
这种方案的优点是简单直观，易于理解。缺点是在某些情况下，例如当数组已经部分排序时，性能会下降，因为每次都选择最后一个元素作为基准值，可能导致分区不平衡。
副标题2： Hoare 分区方案
Hoare 分区方案与 Lomuto 方案不同，它使用两个指针，一个从左向右移动，一个从右向左移动，直到它们相遇。这种方案通常比 Lomuto 方案更有效率，尤其是在处理已经部分排序的数组时。
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);
Hoare 分区方案的关键在于 i 和 j 指针的移动和交换，最终返回 j 作为分区点。需要注意的是，quickSortHoare 递归调用时，右侧子数组的范围是 partitionIndex + 1, high，与 Lomuto 方案略有不同。
副标题3： 随机化快速排序
为了避免快速排序在特定输入下退化成 O(n^2) 的时间复杂度，可以采用随机化快速排序。随机化快速排序的核心是在每次分区时，随机选择一个元素作为基准值。
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); // 使用 Lomuto 分区方案
}
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 分区方案。
副标题4：三种方案的性能比较和选择建议
三种快速排序方案各有优缺点。
- Lomuto 分区方案： 简单易懂，但对于已经部分排序的数组，性能较差。
- Hoare 分区方案： 通常比 Lomuto 方案更有效率，尤其是在处理已经部分排序的数组时。但代码相对复杂一些。
- 随机化快速排序： 通过随机选择基准值，可以有效地避免最坏情况的发生，提高算法的平均性能。
选择哪种方案取决于具体的应用场景。如果对性能要求不高，且数组随机性较好，可以选择 Lomuto 方案。如果需要处理可能已经部分排序的数组，或者对性能有较高要求，可以选择 Hoare 方案或随机化快速排序。 随机化快速排序通常是最佳选择，因为它可以在各种情况下提供良好的平均性能。
副标题5： 快速排序的空间复杂度
快速排序是一种原地排序算法，这意味着它只需要少量的额外空间。在理想情况下（每次分区都将数组分成大致相等的两部分），快速排序的空间复杂度为 O(log n)，这是因为递归调用栈的深度为 log n。 然而，在最坏情况下（每次分区都将数组分成一个空数组和一个包含 n-1 个元素的数组），快速排序的空间复杂度会退化为 O(n)。
通过随机化选择基准值，可以降低最坏情况发生的概率，从而使快速排序的空间复杂度在大多数情况下保持在 O(log n) 级别。
暂无评论内容