方法二：
// 快速排序 const quickSort = (arr, left, right) => { let len = arr.length, partitionIndex; left = typeof left != 'number' ? 0 : left; right = typeof right != 'number' ? len - 1 : right; if (left < right) { partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } return arr; }; const partition = (arr, left, right) => { //分区操作 let pivot = left, //设定基准值（pivot） index = pivot + 1; for (let i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index - 1; }; const swap = (arr, i, j) => { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; };测试
// 测试 const array = [5, 4, 3, 2, 1]; console.log('原始array:', array); const newArr = quickSort(array); console.log('newArr:', newArr); // 原始 array: [5, 4, 3, 2, 1] // newArr: [1, 4, 3, 2, 5]分析
第一，快速排序是原地排序算法吗 ？
因为 partition() 函数进行分区时，不需要很多额外的内存空间，所以快排是原地排序算法。
第二，快速排序是稳定的排序算法吗 ？
和选择排序相似，快速排序每次交换的元素都有可能不是相邻的，因此它有可能打破原来值为相同的元素之间的顺序。因此，快速排序并不稳定。
第三，快速排序的时间复杂度是多少 ？
极端的例子：如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n / 2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。
最佳情况：T(n) = O(nlogn)。
最差情况：T(n) = O(n2)。
平均情况：T(n) = O(nlogn)。
动画
解答开篇问题
快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢 ？
可以发现：
归并排序的处理过程是由下而上的，先处理子问题，然后再合并。
而快排正好相反，它的处理过程是由上而下的，先分区，然后再处理子问题。
归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。
归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。
快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
4. 希尔排序（Shell Sort）思想
先将整个待排序的记录序列分割成为若干子序列。
分别进行直接插入排序。
待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序。
过程
举个易于理解的例子：[35, 33, 42, 10, 14, 19, 27, 44]，我们采取间隔 4。创建一个位于 4 个位置间隔的所有值的虚拟子列表。下面这些值是 { 35, 14 }，{ 33, 19 }，{ 42, 27 } 和 { 10, 44 }。
我们比较每个子列表中的值，并在原始数组中交换它们（如果需要）。完成此步骤后，新数组应如下所示。
然后，我们采用 2 的间隔，这个间隙产生两个子列表：{ 14, 27, 35, 42 }， { 19, 10, 33, 44 }。