【算法】快速排序

* 快速排序实现思路：随机取出一个值进行划分，大于该值放右边，小于该值放左边（该算法在经典快排的基础上经过荷兰国旗思想和随机思想进行了改造）

* 「时间复杂度：O(N*logN)」

* 「空间复杂度：O(logN)」

*

* 快速排序其实就是二叉树中前序遍历的处理方式。

 一、标准方式

function quickSort(arr) {if (arr == null || arr.length <= 0) {// 如果数组为空或者长度为0，返回空数组return [];}quick(arr, 0, arr.length - 1); // 对数组进行快速排序return arr; // 返回排序后的数组
}function quick(arr, L, R) {// 递归结束条件是L>=Rif (L < R) {// 随机找一个值，然后和最后一个值进行交换，将经典排序变为快速排序（因为经典排序每次都是取最后一个数据去对比，对应0,1,2,...,n的情况,其复杂度为O(N^2)）swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R); // 随机选择一个数，将其与最后一个数进行交换// 利用荷兰国旗问题获得划分边界，返回的值是小于区域的最大缩影和大于区域的最小索引，在这利用荷兰国旗问题将等于区域部分就不用动了const tempArr = partition(arr, L, R, arr[R]); // 利用荷兰国旗问题将数组分为三个部分quick(arr, L, tempArr[0]); // 对小于区域进行递归quick(arr, tempArr[1], R); // 对大于区域进行递归}
}// 返回值是小于区域的最后的索引和大于区域的第一个索引
function partition(arr, L, R, num) {var less = L - 1; // 定义小于区域的最后一个索引var more = R + 1; // 定义大于区域的第一个索引var cur = L; // 定义当前索引while (cur < more) {// 当当前索引小于大于区域的第一个索引时if (arr[cur] < num) {// 如果当前值小于num，则将当前值与小于区域的后一个值进行交换，并将小于区域的索引加1，当前索引加1swap(arr, ++less, cur++);} else if (arr[cur] > num) {// 如果当前值大于num，则将当前值与大于区域的前一个值进行交换，并将大于区域的索引减1swap(arr, --more, cur);} else {// 如果当前值等于num，则将当前索引加1cur++;}}return [less, more]; // 返回小于区域的最后一个索引和大于区域的第一个索引
}function swap(arr, i, j) {// 定义交换函数const temp = arr[i]; // 将arr[i]存储到temp中arr[i] = arr[j]; // 将arr[j]赋值给arr[i]arr[j] = temp; // 将temp赋值给arr[j]
}

quickSort函数以数组作为输入并返回排序后的数组。它首先检查数组是否为null或长度为0，如果是，则返回一个空数组。否则，它使用数组、左索引（0）和右索引（arr.length - 1）调用quick函数。

quick函数是快速排序算法的递归实现。它以数组、左索引和右索引作为输入。递归的基本情况是左索引大于或等于右索引。否则，它随机从数组中选择一个枢轴元素并将其与数组中的最后一个元素交换。然后，它使用partition函数将数组分成三部分：小于枢轴的元素、等于枢轴的元素和大于枢轴的元素。然后，它在数组的左部分和右部分上递归调用quick函数。

partition函数以数组、左索引、右索引和枢轴元素作为输入。它使用荷兰国旗算法将数组分成三部分。它维护三个指针：less、more和cur。less指针指向包含小于枢轴的元素的部分中的最后一个元素，more指针指向包含大于枢轴的元素的部分中的第一个元素，cur指针指向正在处理的当前元素。如果当前元素小于枢轴，则将其与less指针处的元素交换，并将less指针递增。如果当前元素大于枢轴，则将其与more指针处的元素交换，并将more指针递减。如果当前元素等于枢轴，则将cur指针递增。该函数返回一个包含包含小于枢轴的元素的部分中的最后一个元素的索引和包含大于枢轴的元素的部分中的第一个元素的索引的数组。

swap函数以数组和两个索引作为输入，并交换这些索引处的元素。

总的来说，这个快速排序的实现在平均情况下具有O(n log n)的时间复杂度，在最坏情况下具有O(n^2)的时间复杂度。最坏情况发生在枢轴元素始终是数组中最小或最大的元素的情况下，这会导致不平衡的分区。

二、优化方式

// 快速排序
function quickSort(arr, left = 0, right = arr.length - 1) {if (left >= right) { // 如果左边界大于等于右边界，直接返回return;}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]]; // 将基准数放到左右两个部分的中间quickSort(arr, left, i - 1); // 对左侧部分进行递归quickSort(arr, i + 1, right); // 对右侧部分进行递归return arr; // 返回排序后的数组
}

该函数接受一个数组arr和两个可选参数left和right，它们表示要排序的子数组的左右索引。如果left大于或等于right，则函数立即返回。否则，函数选择子数组的最右边的元素作为基准数，并将子数组分成两部分：小于基准数的元素和大于或等于基准数的元素。然后，函数递归地对子数组的两部分进行排序。

分区使用两个索引i和j完成。函数使用j从left到right-1遍历子数组。如果arr[j]小于基准数，则函数交换arr[i]和arr[j]并增加i。迭代后，函数交换arr[i]和arr[right]以将基准数放置在正确的位置上。

总体而言，快速排序的平均时间复杂度为O(n log n)，最坏情况下为O(n^2)。

三、测试用例

const arr1 = [3, 0, 2, 5, -1, 4, 1];
console.log(quickSort(arr1)); // [-1, 0, 1, 2, 3, 4, 5]const arr2 = [1, 2, 3, 4, 5];
console.log(quickSort(arr2)); // [1, 2, 3, 4, 5]const arr3 = [5, 4, 3, 2, 1];
console.log(quickSort(arr3)); // [1, 2, 3, 4, 5]