Skip to main content

快速排序-优化版本

由于快速排序的思路比较抽象，需要对分治和递归等概念有一定的理解，因此初学者可能会感到较为复杂。​

  1. 首先调用 quickSort 函数，传入要排序的数组 [52, 63, 14, 59, 68, 35, 8, 67, 45, 99]，以及左右边界 0 和 arr.length - 1。

  2. 在 quickSort 函数内部，首先进行边界检查，发现左边界小于右边界，因此需要继续排序。

  3. 接着调用 partition 函数，传入要排序的数组 [52, 63, 14, 59, 68, 35, 8, 67, 45, 99]，以及左右边界 0 和 9。

  4. 在 partition 函数内部，首先将基准元素 99 保存下来，并将其移到数组的最右侧，即将数组变为 [52, 63, 14, 59, 68, 35, 8, 67, 45, 99]。

  5. 接着定义一个 storeIndex 变量为 0，然后从左到右遍历数组。第一个数 52 小于基准元素 99，因此将其与 storeIndex 处的数 52 交换，将数组变为 [52, 63, 14, 59, 68, 35, 8, 67, 45, 99]。同时将 storeIndex 加 1，变为 1。

  6. 接下来遍历到数 63，大于基准元素 99，不需要交换。继续遍历到数 14，小于基准元素 99，因此将其与 storeIndex 处的数 63 交换，将数组变为 [52, 14, 63, 59, 68, 35, 8, 67, 45, 99]。同时将 storeIndex 加 1，变为 2。

  7. 继续遍历数组，直到遍历到数 45 时，将其与 storeIndex 处的数 68 交换，将数组变为 [52, 14, 63, 59, 45, 35, 8, 67, 68, 99]。同时将 storeIndex 加 1，变为 3。

  8. 遍历结束后，将基准元素 99 移动到 storeIndex 处，即将数组变为 [52, 14, 63, 59, 45, 35, 8, 67, 68, 99]。

  9. partition 函数返回 storeIndex，即 9，作为新的基准元素位置。

  10. 回到 quickSort 函数内部，将数组分成左右两部分，分别为 [52, 14, 63, 59, 45, 35, 8, 67, 68]

  11. 接着对左半部分 [52, 14, 63, 59, 45, 35, 8, 67, 68] 进行递归调用 quickSort 函数，传入左右边界 0 和 8。

  12. 在新的 quickSort 函数内部，进行边界检查，发现左边界小于右边界，因此需要继续排序。

  13. 接着调用 partition 函数，传入左半部分数组 [52, 14, 63, 59, 45, 35, 8, 67, 68]，以及左右边界 0 和 7。

  14. 在 partition 函数内部，首先将基准元素 68 保存下来，并将其移到数组的最右侧，即将数组变为 [52, 14, 63, 59, 45, 35, 8, 67, 68]。

  15. 接着定义一个 storeIndex 变量为 0，然后从左到右遍历数组。第一个数 52 小于基准元素 68，因此将其与 storeIndex 处的数 52 交换，将数组变为 [52, 14, 63, 59, 45, 35, 8, 67, 68]。同时将 storeIndex 加 1，变为 1。

  16. 继续遍历数组，直到遍历到数 35 时，将其与 storeIndex 处的数 63 交换，将数组变为 [52, 14, 35, 59, 45, 63, 8, 67, 68]。同时将 storeIndex 加 1，变为 2。

  17. 遍历结束后，将基准元素 68 移动到 storeIndex 处，即将数组变为 [52, 14, 35, 59, 45, 63, 8, 67, 68]。

  18. partition 函数返回 storeIndex，即 8，作为新的基准元素位置。

  19. 回到新的 quickSort 函数内部，将左半部分 [52, 14, 35, 59, 45, 63, 8, 67] 分成左右两部分，分别为 [52, 14, 35, 45, 8] 和 [59, 63, 67]。

  20. 对左半部分 [52, 14, 35, 45, 8] 进行递归调用 quickSort 函数，传入左右边界 0 和 4。

  21. 在新的 quickSort 函数内部，进行边界检查，发现左边界小于右边界，因此需要继续排序。

  22. 接着调用 partition 函数，传入左半部分数组 [52, 14, 35, 45, 8]，以及左右边界 0 和 3。

  23. 在 partition 函数内部，首先将基准元素 8 保存下来，并将其移到数组的最右侧，即将数组变为 [52, 14, 35, 45, 8]。

  24. 接着定义一个 storeIndex 变量为 0，然后从左到右遍历数组。第一个数 52 大于基准元素 8，因此不需要交换位置。同时将 storeIndex 加 1，变为 1。

  25. 继续遍历数组，直到遍历到数 45 时，将其与 storeIndex 处的数 14 交换，将数组变为 [52, 45, 35, 14, 8]。同时将 storeIndex 加 1，变为 2。

  26. 遍历结束后，将基准元素 8 移动到 storeIndex 处，即将数组变为 [52, 45, 35, 14, 8]。

  27. partition 函数返回 storeIndex，即 4，作为新的基准元素位置。

  28. 回到新的 quickSort 函数内部，将左半部分 [52, 45, 35, 14, 8] 分成左右两部分，分别为 [45, 35, 14, 8] 和 [52]。

  29. 对左半部分 [45, 35, 14, 8] 进行递归调用 quickSort 函数，传入左右边界 0 和 3。

  30. 在新的 quickSort 函数内部，进行边界检查，发现左边界小于右边界，因此需要继续排序。

  31. 接着调用 partition 函数，传入左半部分数组 [45, 35, 14, 8]，以及左右边界 0 和 2。

  32. 在 partition 函数内部，首先将基准元素 8 保存下来，并将其移到数组的最右侧，即将数组变为 [45, 35, 14, 8]。

  33. 接着定义一个 storeIndex 变量为 0，然后从左到右遍历数组。第一个数 45 大于基准元素 8，因此不需要交换位置。同时将 storeIndex 加 1，变为 1。

  34. 继续遍历数组，直到遍历到数 14 时，将其与 storeIndex 处的数 35 交换，将数组变为 [45, 14, 35, 8]。同时将 storeIndex 加 1，变为 2。

  35. 继续遍历数组，直到遍历到数 8 时，将其与 storeIndex 处的数 45 交换，将数组变为 [8, 14, 35, 45]。同时将 storeIndex 加 1，变为 3。

  36. 遍历结束后，将基准元素 8 移动到 storeIndex 处，即将数组变为 [8, 14, 35, 45]。

  37. partition 函数返回 storeIndex，即 0，作为新的基准元素位置。

  38. 回到新的 quickSort 函数内部，将左半部分 [8, 14, 35, 45] 分成左右两部分，分别为 [] 和 [8, 14, 35, 45]。

  39. 对左半部分 [] 进行递归调用 quickSort 函数，传入左右边界 0 和 -1。由于左边界大于右边界，因此不需要排序。

  40. 对右半部分 [8, 14, 35, 45] 进行递归调用 quickSort 函数，传入左右边界 0 和 3。

  41. 在新的 quickSort 函数内部，进行边界检查，发现左边界小于右边界，因此需要继续排序。

  42. 接着调用 partition 函数，传入左半部分数组 [8, 14, 35, 45]，以及左右边界 0 和 2。

  43. 在 partition 函数内部，首先将基准元素 14 保存下来，并将其移到数组的最右侧，即将数组变为 [8, 35, 45, 14]。

  44. 接着定义一个 storeIndex 变量为 0，然后从左到右遍历数组。第一个数 8 小于基准元素 14，因此将其与 storeIndex 处的数 35 交换，将数组变为 [35, 8, 45, 14]。同时将 storeIndex 加 1，变为 1。

  45. 继续遍历数组，直到遍历到数 45 时，将其与 storeIndex 处的数 8 交换，将数组变为 [35, 8, 45, 14]。同时将 storeIndex 加 1，变为 2。

  46. 遍历结束后，将基准元素 14 移动到 storeIndex 处，即将数组变为 [35, 8, 14, 45]。

  47. partition 函数返回 storeIndex，即 2，作为新的基准元素位置。

  48. 回到新的 quickSort 函数内部，将左半部分 `[35, 8, 14]

  49. 将左半部分 [35, 8, 14] 分成左右两部分，分别为 [8] 和 [35, 14]。

  50. 对左半部分 [8] 进行递归调用 quickSort 函数，传入左右边界 0 和 0。由于只有一个元素，不需要排序。

  51. 对右半部分 [35, 14] 进行递归调用 quickSort 函数，传入左右边界 0 和 1。

  52. 在新的 quickSort 函数内部，进行边界检查，发现左边界小于右边界，因此需要继续排序。

  53. 接着调用 partition 函数，传入左半部分数组 [35, 14]，以及左右边界 0 和 0。

  54. 在 partition 函数内部，首先将基准元素 35 保存下来，并将其移到数组的最右侧，即将数组变为 [14, 35]。

  55. 接着定义一个 storeIndex 变量为 0，然后从左到右遍历数组。第一个数 14 小于基准元素 35，因此将其与 storeIndex 处的数 14 交换，将数组变为 [14, 35]。同时将 storeIndex 加 1，变为 1。

  56. 遍历结束后，将基准元素 35 移动到 storeIndex 处，即将数组变为 [14, 35]。

  57. partition 函数返回 storeIndex，即 1，作为新的基准元素位置。

  58. 回到新的 quickSort 函数内部，将左半部分 [14] 分成左右两部分，分别为 [] 和 [14]。

  59. 对左半部分 [] 进行递归调用 quickSort 函数，传入左右边界 0 和 -1。由于左边界大于右边界，因此不需要排序。

  60. 对右半部分 [14] 进行递归调用 quickSort 函数，传入左右边界 0 和 0。由于只有一个元素，不需要排序。

  61. 排序结束，最终数组变为 [8, 14, 35, 45, 52, 59, 63, 67, 68, 99]。

快速排序-优化版本​

以下是一个更高效的快速排序实现，它采用了原地排序（in-place sorting）和 三项取中法（median-of-three partitioning）优化，可以在处理大型数组时提高性能。

解析实现: quickSort 函数，它接受一个数组参数 arr，以及可选的两个参数 left 和 right，用于指定排序范围的左右边界。 在函数内部，通过检查左右边界是否合法（即左边界小于右边界），来决定是否需要递归调用自身进行排序。 如果需要排序，则调用 partition 函数来对数组进行划分，然后递归调用 quickSort 函数对划分后的 左右两部分分别进行排序。最终返回排序后的数组 arr。

接下来是 partition 函数的定义，它用于对数组进行划分，将小于基准元素的数放到左边，大于基准元素的数放到右边。 该函数接受四个参数，分别是要排序的数组 arr，排序范围的左右边界 left 和 right，以及基准元素的下标 pivotIndex。 该函数首先将基准元素 pivotValue 保存下来，然后将其移到数组的最右侧（这样可以避免在后面的遍历过程中再次访问到基准元素，提高效率）。

partition 函数则是实现了原地排序，它通过遍历数组并将小于基准元素的元素 移动到数组左侧来实现。

接着，函数定义了一个 storeIndex 变量，用于记录小于基准元素的数应该插入的位置。 然后从左到右遍历数组，如果当前数小于基准元素，则将其与 storeIndex 处的数交换，并将 storeIndex 加 1， 表示已经有一个小于基准元素的数被放到了左侧。遍历结束后，将基准元素移到 storeIndex 处， 然后返回该位置作为新的基准元素位置。

function quickSort(arr, left = 0, right = arr.length - 1) {
  console.log('quickSort:', { arr, left, right })
  debugger
  if (left < right) {
    const pivotIndex = getPivotIndex(arr, left, right);
    const newPivotIndex = partition(arr, left, right, pivotIndex);
    quickSort(arr, left, newPivotIndex - 1);
    quickSort(arr, newPivotIndex + 1, right);
  }
  return arr;
}

function getPivotIndex(arr, left, right) {
  const mid = Math.floor((left + right) / 2);
  if (arr[left] > arr[mid]) {
    swap(arr, left, mid);
  }
  if (arr[left] > arr[right]) {
    swap(arr, left, right);
  }
  if (arr[mid] > arr[right]) {
    swap(arr, mid, right);
  }
  return mid;
}

function partition(arr, left, right, pivotIndex) {
  const pivotValue = arr[pivotIndex];
  swap(arr, pivotIndex, right);
  let storeIndex = left;
  for (let i = left; i < right; i++) {
    if (arr[i] < pivotValue) {
      swap(arr, i, storeIndex);
      storeIndex++;
    }
  }
  swap(arr, storeIndex, right);
  return storeIndex;
}

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

const arr = [52, 63, 14, 59, 68, 35, 8, 67, 45, 99];
quickSort(arr);
console.log(arr); // [8, 14, 35, 45, 52, 59, 63, 67, 68, 99]