快速排序是一种高效的排序算法，采用分治策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。
快速排序的基本原理
快速排序的基本思想是选择一个基准元素（通常选择第一个或最后一个元素），通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
选择基准元素
选择基准元素的方式有多种。最简单的方法是选取序列中的第一个元素作为基准。除此之外，还可以采用随机选取、三数取中等方法来选择基准元素，以减少排序过程中出现的最坏情况。
分区过程
分区过程是快速排序的核心，它负责将基准元素放到正确的位置，并确保所有小于基准的元素都在基准的左侧，所有大于基准的元素都在基准的右侧。
实现分区的步骤
- 初始化：设置两个指针
left和right，分别指向序列的起始位置和结束位置。 - 移动指针：从右向左移动
right指针，直到找到一个小于基准的元素；再从左向右移动left指针，直到找到一个大于基准的元素。 - 交换元素：交换这两个指针所指向的元素。
- 重复上述步骤：直到
left和right相遇。 - 基准就位：将基准元素与相遇点的元素交换位置。
递归排序
完成一次分区后，基准元素已经处于最终位置。接下来，对基准左右两侧的子序列递归地进行快速排序。
JavaScript 中的快速排序实现
下面是一个简单的快速排序的实现：
// www.javascriptcn.com code example
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;
}
function partition(arr, left, right) {
const pivot = arr[left]; // 选取基准元素
let low = left + 1; // 初始化低指针
let high = right; // 初始化高指针
while (true) {
// 从左向右移动，直到找到一个大于或等于基准的元素
while (low <= high && arr[high] >= pivot) {
high--;
}
// 从右向左移动，直到找到一个小于或等于基准的元素
while (low <= high && arr[low] <= pivot) {
low++;
}
if (low <= high) {
// 如果两者都没有相遇，则交换它们
[arr[low], arr[high]] = [arr[high], arr[low]];
} else {
// 如果两者已经相遇，则退出循环
break;
}
}
// 将基准元素放置到正确位置
[arr[left], arr[high]] = [arr[high], arr[left]];
return high; // 返回基准元素的位置
}示例
const array = [8, 4, 23, 42, 16, 15]; console.log(quickSort(array)); // 输出: [4, 8, 15, 16, 23, 42]
性能分析
快速排序的时间复杂度在最好情况下为O(n log n)，在最坏情况下为O(n^2)，平均情况下为O(n log n)。空间复杂度为O(log n)，因为递归调用栈需要额外的空间。
快速排序在大多数情况下表现优秀，尤其是当数据分布均匀时。但当数据已经部分排序或者完全逆序时，其性能会显著下降。为了改善这种情况，可以使用随机化版本的快速排序或者选择合适的基准元素策略。
总结
快速排序是一种非常实用且高效的排序算法，广泛应用于各种场景中。通过合理的选择基准元素和优化分区过程，可以进一步提高其效率和稳定性。