快速排序是一种基于分治法的排序算法。它通过不断地将数组分成较小的子数组，并按照递归的方式对每个子数组进行排序，最终将整个数组排序。
快速排序算法的原理如下：
- 从待排序数组中选择一个元素作为枢轴元素。
- 将小于枢轴元素的所有元素移动到枢轴元素的左边，大于枢轴元素的所有元素移动到枢轴元素的右边。
- 对左子数组和右子数组进行递归调用快速排序算法，直至子数组只剩一个元素或为空。
- 递归结束后，整个数组就变得有序。
通过不断地选择枢轴元素并分割数组，快速排序算法可以将数组划分为越来越小的子数组，直到最后将整个数组排序完成。该算法的时间复杂度为O(nlogn)。
通常采用双指针法来找到基准元素的正确位置。首先，将左指针指向数组的起始位置，右指针指向数组的末尾位置。然后，左指针从左往右移动，直到找到比基准元素大的元素，并停止。右指针从右往左移动，直到找到比基准元素小的元素，并停止。接着，交换左右指针所指向的元素。重复上述步骤，直到左指针和右指针相遇。最后，将基准元素与左指针所指向的元素进行交换，使得基准元素位于正确的位置
具体实现如下：
// 定义一个交换函数，用于交换数组中的两个元素
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
// 定义一个分区函数，用于对数组进行分区操作
function partition(arr, left, right) {
const pivot = arr[right - 1]; // 将分区点设置为最右边的元素
let i = left,
j = right - 1; // 初始化指针i和j
while (i !== j) {
// 当i和j指针不相遇时，进行循环
arr[i] <= pivot ? i++ : swap(arr, i, --j); // 如果arr[i]小于等于分区点，则i指针向右移动；否则进行交换，并将j指针向左移动
}
swap(arr, j, right - 1); // 将分区点放置在正确的位置
return j; // 返回分区点的索引
}
// 定义一个快速排序函数
function qsort(arr, left = 0, right = arr.length) {
if (right - left <= 1) return; // 当要排序的元素个数小于等于1时，直接返回
const p = partition(arr, left, right); // 进行分区操作，并获取分区点的索引p
qsort(arr, left, p); // 对分区点左侧的子数组进行快速排序
qsort(arr, p + 1, right); // 对分区点右侧的子数组进行快速排序
}
const arr = [5, 3, 8, 4, 2, 1, 10, 11, -4, 55];
qsort(arr); // [ -4, 1, 2, 3, 4, 5, 8, 10, 11, 55 ]
console.log(arr);
其他的一下实现方式：
/**
1. 第一段程序使用的是递归的方式实现快速排序。它选择数组中间的元素作为基准元素，然后将数组分割为左右两个子数组，将比基准元素小的元素放在左子数组，将比基准元素大的元素放在右子数组，然后递归地对左右两个子数组进行快速排序，最后将左右两个子数组和基准元素拼接起来作为排序结果。
2. 第二段程序使用的是基于指针的方式实现快速排序。它通过定义一个分区函数来选择基准元素，并将数组分割为左右两个子数组，然后再递归地对左右两个子数组进行快速排序。分区函数中使用了双指针的方法，从左到右找到第一个大于基准元素的元素，从右到左找到第一个小于基准元素的元素，然后交换它们的位置。这样，最终基准元素的位置就确定下来了，并且左边的元素都小于等于基准元素，右边的元素都大于基准元素。
总的来说，这两段程序的思路是相同的，都是通过不断地将数组分割为更小的子数组并排序，最后再将子数组合并成排序后的结果。它们的实现细节略有不同，但最终的结果是相同的。
*/
//---------------------------------1------------------------------------
function quickSort(arr) {
// 如果数组长度小于等于1，则直接返回
if (arr.length <= 1) {
return arr;
}
// 选择一个基准元素
const pivot = arr[Math.floor(arr.length / 2)];
// 定义左右两个子数组
const left = [];
const right = [];
// 将元素分割到左右两个子数组
for (let i = 0; i < arr.length; i++) {
if (i === Math.floor(arr.length / 2)) {
continue; // 跳过基准元素
}
if (arr[i] <= pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 递归地对左右两个子数组进行快速排序
return quickSort(left).concat([pivot], quickSort(right));
}
// 测试
const arr = [5, 3, 8, 4, 2, 1, 10];
const sortedArr = quickSort(arr);
console.log(sortedArr); // 输出 [1, 2, 3, 4, 5, 8, 10]
//---------------------------------2------------------------------------
// 快速排序函数
function quickSort1(arr, left, right) {
// 递归结束条件
if (left >= right) {
return;
}
// 设置左右指针及基准值
let pivot = arr[left];
let i = left;
let j = right;
// 开始一轮排序
while (i < j) {
// 从右侧找到比基准值小的元素
while (i < j && arr[j] >= pivot) {
j--;
}
// 将该元素放到左侧
arr[i] = arr[j];
// 从左侧找到比基准值大的元素
while (i < j && arr[i] <= pivot) {
i++;
}
// 将该元素放到右侧
arr[j] = arr[i];
}
// 将基准值放回数组
arr[i] = pivot;
// 递归调用快速排序函数对左右两个子数组进行排序
quickSort1(arr, left, i - 1);
quickSort1(arr, i + 1, right);
}
// 测试
let arr2 = [5, 8, 2, 6, 3, 9, 1, 7, 4];
quickSort1(arr2, 0, arr2.length - 1);
console.log(arr2);
