排序算法

快速排序 空间复杂度         首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；      最优的情况下空间复杂度为：O(logn)  ；每一次都平分数组的情况      最差的情况下空间复杂度为：O( n )      ；退化为冒泡排序的情况 时间复杂度 最优情况下时间复杂度          快速排序最优的情况就是每一次取到的元素都刚好平分整个数组；         此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；     快速排序最优的情况下时间复杂度为：O( nlogn ) 最差情况下时间复杂度         最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)      快速排序最差的情况下时间复杂度为：O( n^2 ) 平均时间复杂度         快速排序的平均时间复杂度也是：O(nlogn)

补充

补充：快速排序的核心是「分治 + 哨兵划分」，平均 O(nlogn)，最坏 O(n²)，空间 O(logn)~O(n)，是不稳定排序。

JavaScript 实现（in-place）：

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;
  const pivotIdx = partition(arr, left, right);
  quickSort(arr, left, pivotIdx - 1);
  quickSort(arr, pivotIdx + 1, right);
  return arr;
}

function partition(arr, left, right) {
  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]];
  return i;
}

常见优化：

• 三数取中：避免选到极值导致最坏情况。
• 随机化哨兵：选 pivot 时随机索引，降低被构造数据击溃的概率。
• 小数组切换插入排序：当区间长度 ≤ 10 时改用插入排序。
• 尾递归 / 迭代：减少递归栈深度。

补充：V8 的 Array.prototype.sort 在元素较少时用插入排序，规模较大时用 TimSort（基于归并+插入的稳定排序），而不是快速排序。