快速排序：高效排序算法详解
快速排序是一种基于分治策略的高效排序算法。其核心思想是：每次选取一个元素作为枢轴（pivot），将数组划分成两部分，一部分小于枢轴，一部分大于枢轴，然后递归地对这两部分进行排序。
枢轴的正确位置
枢轴元素的正确位置是指：所有小于枢轴的元素位于其左侧，所有大于枢轴的元素位于其右侧。 需要注意的是，左右两侧的元素不必有序，枢轴元素处于正确位置即可。
例如，对于枢轴值为 23 的数组，以下几种情况都满足条件：
1
2
3
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]
寻找枢轴的正确位置
快速排序算法通过一系列比较和交换操作来确定枢轴的正确位置。 让我们以数组 [10, 4, 15, 6, 23, 40, 1, 17, 7, 8] 为例，其中 10 为枢轴：
算法会依次遍历数组，统计小于枢轴的元素个数。 如果遇到小于枢轴的元素，则需要将枢轴向前移动，为其腾出空间。
这个过程会持续到数组末尾。最终，算法会确定枢轴需要移动的步数，从而找到其正确位置。
代码示例 (JavaScript)
以下代码展示了快速排序算法的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function partition(arr, left, right) {
const pivot = arr[left];
let i = left + 1, j = right;
while (i <= j) {
while (i <= j && arr[i] <= pivot) i++;
while (i <= j && arr[j] > pivot) j--;
if (i < j) [arr[i], arr[j]] = [arr[j], arr[i]];
}
[arr[left], arr[j]] = [arr[j], arr[left]];
return j;
}
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
const pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}
// 示例用法
const arr = [10, 4, 15, 6, 23, 40, 1, 17, 7, 8];
const sortedArr = quickSort(arr);
console.log(sortedArr); // 输出已排序的数组
快速排序通过递归地将数组划分成更小的子数组，并利用枢轴元素的正确位置来高效地完成排序。 其平均时间复杂度为 O(n log n)，但在最坏情况下（例如数组已排序）时间复杂度会退化为 O(n²)。
以上就是学习快速排序算法的详细内容，更多请关注php中文网其它相关文章！