三天精通一算法之快速排序
力扣链接912. 排序数组 - 力扣（LeetCode）注意这题快排不能用递归，否则堆会爆
快速排序（Quicksort）是一种高效的排序算法，通常使用分治法来将一个列表分成较小的子列表，然后递归地排序这些子列表。以下是用 JavaScript 实现快速排序的几种方式：
### 方法一：标准递归实现
```javascript
function quickSort(arr) {
// 如果数组长度小于等于1，则直接返回（已排序）
if (arr.length <= 1) {
return arr;
}
// 选择基准元素（这里选择中间元素）
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
// 定义左右两个数组
const left = [];
const right = [];
// 遍历数组（跳过基准元素），根据与基准元素的比较结果放入left或right
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) continue; // 跳过基准元素
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 递归调用quickSort并合并结果
return [...quickSort(left), pivot, ...quickSort(right)];
}
// 示例使用
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSort(unsortedArray)); // 输出: [1, 1, 2, 3, 6, 8, 10]
```
### 方法二：原地排序（in-place）
这种方法不需要额外的空间来存储 `left` 和 `right` 数组，而是通过交换元素在原数组上进行排序。
```javascript
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) {
return arr;
}
// 分区函数，返回分区点索引
function partition(arr, left, right) {
const pivot = arr[right]; // 选择最右边的元素作为基准
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]]; // 交换
i++;
}
}
// 将基准元素放到正确的位置
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
// 获取分区点
const pivotIndex = partition(arr, left, right);
// 递归对左右两部分进行排序
quickSortInPlace(arr, left, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, right);
return arr;
}
// 示例使用
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSortInPlace(unsortedArray)); // 输出: [1, 1, 2, 3, 6, 8, 10]
```
### 方法三：随机化快速排序
为了减少最坏情况的发生概率（例如当输入已经是排序好的数组时），可以选择一个随机的基准元素来进行分区。
```javascript
function quickSortRandomized(arr, left = 0, right = arr.length - 1) {
if (left >= right) {
return arr;
}
function partition(arr, left, right) {
const randomPivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
[arr[randomPivotIndex], arr[right]] = [arr[right], arr[randomPivotIndex]]; // 交换随机基准到末尾
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]]; // 交换
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]]; // 将基准元素放到正确的位置
return i;
}
const pivotIndex = partition(arr, left, right);
quickSortRandomized(arr, left, pivotIndex - 1);
quickSortRandomized(arr, pivotIndex + 1, right);
return arr;
}
// 示例使用
const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSortRandomized(unsortedArray)); // 输出: [1, 1, 2, 3, 6, 8, 10]
```
这三种方法展示了不同的快速排序实现方式。第一种是最简单的递归实现，第二种是更高效的原地排序，而第三种则是引入了随机化以提高性能稳定性。你可以根据具体需求选择最适合的方法。
原文地址：https://blog.csdn.net/ghw666666/article/details/144378768
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！