快速排序算法详解

快速排序算法详解

快速排序是一种基于分治策略的高效排序算法。其核心思想是：每次选取一个元素作为枢轴（pivot），将数组划分成两部分，一部分小于枢轴，一部分大于枢轴，然后递归地对这两部分进行排序。

枢轴的正确位置

枢轴元素的正确位置是指：所有小于枢轴的元素位于其左侧，所有大于枢轴的元素位于其右侧。 需要注意的是，左右两侧的元素不必有序，枢轴元素处于正确位置即可。

例如，对于枢轴值为 23 的数组，以下几种情况都满足条件：

[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 为枢轴：

算法会依次遍历数组，统计小于枢轴的元素个数。 如果遇到小于枢轴的元素，则需要将枢轴向前移动，为其腾出空间。

例如，遇到 4 和 6 时，需要将它们与大于 10 的元素交换位置，以确保小于 10 的元素都位于 10 的左侧。

这个过程会持续到数组末尾。最终，算法会确定枢轴需要移动的步数，从而找到其正确位置。

代码示例 (JavaScript)

以下代码展示了快速排序算法的实现：

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²)。