学习快速排序算法

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

快速排序的工作原理

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

当:

时，枢轴元素位于正确位置

1. 其左侧的所有元素都较小。
2. 其右侧的所有元素都较大。

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

// 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 是主元:

此时：

• 数字 10 不知道它是否处于正确的位置，也不知道它需要移动多少步才能到达那里。快速排序首先将 10 与下一个索引处的值进行比较。
• 当发现 4 较小时，快速排序记录枢轴需要向前移动一步才能让 4 出现在它之前。
• 因此 numberOfStepsToMove 增加 1。

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

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

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

快速排序继续循环遍历数组，根据小于主元的数字数量增加 numberOfStepsToMove。这有助于确定枢轴需要移动多远才能到达正确位置。

numberOfStepsToMove 不会改变 23 或 40，因为这两个值都大于基准值，并且在数组中不应位于基准值之前：

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

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

现在我们已经到达了数组的末尾，我们知道有 5 个数字小于 10。因此，主元 (10) 必须向前移动 5 步到其正确位置，该位置大于所有数字前面的数字。

让我们看看代码中的样子:

// 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]

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

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;
};

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

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);
}

• 算法递归地对包含小于主元的元素的左子数组进行排序。
• 当子数组有一个或零个元素时，递归停止，因为它已经排序。

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

// 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]

在此示例中，右侧已经排序，但算法不知道这一点，如果没有排序，它也会被排序。

以上是学习快速排序算法的详细内容。更多信息请关注PHP中文网其他相关文章！