快速排序算法

快速排序是最有效的算法之一，它使用分治技术对数组进行排序。

快速排序的工作原理

快速排序的主要思想是帮助未排序数组中的一个元素一次移动到其正确位置。这个元素称为“枢轴”。

**当满足以下条件时，枢轴元素处于正确的位置**：

左侧或右侧的数字是否已排序并不重要。重要的是“枢轴”在数组中处于正确的位置。

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

所有这些都是“枢轴”为“23”的数组的有效输出。

找到枢轴的正确位置

快速排序可帮助“基准”在数组中找到其正确位置。例如，如果“基准”位于数组的开头但不是最小数字，则快速排序确定需要移动 5 步来为数组中的 5 个较小元素腾出空间——假设有 5 个这样的数字。

**假设我们有这个数组：[10, 4, 15, 6, 23, 40, 1, 17, 7, 8]，其中 10 是枢轴**：

**在此刻**：

接下来，在索引 2 处，值为 `15`，大于 `10`。由于不需要进行调整，**快速排序保持步数不变**并继续处理数组中的下一个元素。

在下一个索引处，值为“6”，小于“10”。快速排序**将步数增加到 2**，因为“pivot”现在需要为两个较小的数字腾出空间：“4”和“6”。

现在，需要将“6”与“15”交换，以使较小的数字在数组左侧彼此相邻。我们根据当前索引和“numberOfStepsToMove”值交换数字。

快速排序继续循环遍历数组，根据比“基准”小的数字数量增加“移动步数”。这有助于确定基准需要移动到正确位置的距离。

“numberOfStepsToMove” 不会因 “23” 或 “40” 而改变，因为这两个值都大于 “pivot” 并且不应该在数组中位于它之前：

现在，当快速排序循环到索引 6 处的值 `1` 时，`numberOfStepsToMove` 会增加到 `3`，并将其交换为索引 `3` 处的数字：

快速排序继续此过程，直到到达数组末尾：

现在我们已经到达数组的末尾，我们知道有 5 个数字小于 10。因此，“枢轴”（10）必须向前移动 5 步到达其正确位置，在该位置它大于它之前的所有数字。

**让我们看看代码中是怎样的**：

const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => {
  let numberOfStepsToMove = start;
  // we're picking the first element in the array as the pivot
  const pivot = arr[start];

  // start checking the next elements to the pivot
  for (let i = start + 1; i <= end; i++) {
    // is the current number less than the pivot?
    if (arr[i] < pivot) {
      // yes - so w should increase numberOfStepsToMove
// or the new index of the pivot
      numberOfStepsToMove++;

      // now swap the number at the index of numberOfStepsToMove with the smaller one
      [arr[i], arr[numberOfStepsToMove]] = [arr[numberOfStepsToMove], arr[i]];
    } else {
      // what if it's greater?
      // do nothing -- we need to move on to the next number
      // to check if we have more numbers less that pivot to increase numberOfStepsToMove or not
    }
  }

  // now we know the pivot is at arr[start] and we know that it needs to move numberOfStepsToMove
  // so we swap the numbers to place the pivot number to its correct position
  [arr[start], arr[numberOfStepsToMove]] = [
    arr[numberOfStepsToMove],
    arr[start],
  ];

  return numberOfStepsToMove;
};

现在我们有一个函数来帮助我们找到放置枢轴的位置，让我们看看 Qucik Sort 如何将数组分成更小的数组，并利用 `getNumberOfStepsToMove` 函数来放置所有数组元素。

function quickSort(arr, left = 0, right = arr.length - 1) {
  // pivotIndex the new index of the pivot in in the array
  // in our array example, at the first call this will be 5, because we are checking 10 as the pivot
  // on the whole array
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);
}

快速排序利用递归有效地将数组划分为更小的子数组，并通过与“枢轴”进行比较来确保对元素进行排序。

function quickSort(arr, left = 0, right = arr.length - 1) {
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);

  // the function starts calling itself from the beginning of the array where left = 0;
  // and right is the index before pivotIndex (4 when pivotIndex is 5)
  quickSort(arr, left, pivotIndex - 1);

 //Reaching this point means that the left side of the array is fully
// sorted, with each element positioned in its correct place

  return arr;
}

现在我们需要对数组的右侧执行相同的过程：

function quickSort(arr, left = 0, right = arr.length - 1) {
  // if the right index is greater, the sorting is done and we should return the array
  if (left < right) {
    let pivotIndex = getNumberOfStepsToMove(arr, left, right);

    // the function starts calling itself from the beginning of the array where left = 0;
    // and right is the index before pivotIndex (4 when pivotIndex is 4)
    quickSort(arr, left, pivotIndex - 1);

    // we then call the function from the index after the pivotIndex until the end of the array to handle the right subarray
    quickSort(arr, pivotIndex + 1, right);
  }

  // now all is sorted and placed correctly to the array
  return arr;
}

在这个例子中，右侧已经排序好了，但是算法不知道这一点，如果没有排序的话，它就已经排序好了。