快速排序是最有效的算法之一，它使用分治技術(shù)對數(shù)組進行排序。

快速排序的工作原理

快速排序的主要思想是幫助一次將一個元素移動到未排序數(shù)組中的正確位置。這個元素稱為樞軸。

當:

時，樞軸元素位于正確位置

1. 其左側(cè)的所有元素都較小。
2. 其右側(cè)的所有元素都較大。

左邊或右邊的數(shù)字是否已排序并不重要。重要的是樞軸位于數(shù)組中的正確位置。

// 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 的數(shù)組的有效輸出。

找到樞軸的正確位置

快速排序幫助樞軸找到其在數(shù)組中的正確位置。例如，如果樞軸位于數(shù)組的開頭但不是最小的數(shù)字，則快速排序確定需要移動 5 步才能為數(shù)組中的 5 個較小元素騰出空間 - 假設(shè)有 5 個這樣的元素數(shù)字。

假設(shè)我們有數(shù)組：[10, 4, 15, 6, 23, 40, 1, 17, 7, 8]，10 是主元:

此時：

• 數(shù)字 10 不知道它是否處于正確的位置，也不知道它需要移動多少步才能到達那里?？焖倥判蚴紫葘?10 與下一個索引處的值進行比較。
• 當發(fā)現(xiàn) 4 較小時，快速排序記錄樞軸需要向前移動一步才能讓 4 出現(xiàn)在它之前。
• 因此 numberOfStepsToMove 增加 1。

接下來，在索引 2 處，值為 15，大于 10。由于不需要調(diào)整，快速排序保持步數(shù)不變并移至數(shù)組中的下一個元素。

在下一個索引處，值為 6，小于 10。快速排序 將步數(shù)增加到 2，因為主元現(xiàn)在需要為兩個較小的數(shù)字騰出空間：4 和 6 .

現(xiàn)在，6 需要與 15 交換，以保持較小的數(shù)字在數(shù)組的左側(cè)彼此相鄰。我們根據(jù)當前索引和 numberOfStepsToMove 值交換數(shù)字。

快速排序繼續(xù)循環(huán)遍歷數(shù)組，根據(jù)小于主元的數(shù)字數(shù)量增加 numberOfStepsToMove。這有助于確定樞軸需要移動多遠才能到達正確位置。

numberOfStepsToMove 不會改變 23 或 40，因為這兩個值都大于基準值，并且在數(shù)組中不應位于基準值之前：

現(xiàn)在，當快速排序循環(huán)到索引 6 處的值 1 時，numberOfStepsToMove 增加到 3 并交換索引 3 處的數(shù)字：

快速排序繼續(xù)此過程，直到到達數(shù)組末尾：

現(xiàn)在我們已經(jīng)到達了數(shù)組的末尾，我們知道有 5 個數(shù)字小于 10。因此，主元 (10) 必須向前移動 5 步到其正確位置，該位置大于所有數(shù)字前面的數(shù)字。

讓我們看看代碼中的樣子:

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

現(xiàn)在我們有了一個函數(shù)來幫助我們找到放置樞軸的位置，讓我們看看 Qucik Sort 如何將數(shù)組劃分為更小的數(shù)組，并利用 getNumberOfStepsToMove 函數(shù)來放置所有數(shù)組元素。

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

快速排序利用遞歸將數(shù)組有效地劃分為更小的子數(shù)組，確保通過將元素與主元進行比較來對元素進行排序。

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

• 算法遞歸地對包含小于主元的元素的左子數(shù)組進行排序。
• 當子數(shù)組有一個或零個元素時，遞歸停止，因為它已經(jīng)排序。

現(xiàn)在我們需要對數(shù)組的右側(cè)執(zhí)行相同的過程：

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

在此示例中，右側(cè)已經(jīng)排序，但算法不知道這一點，如果沒有排序，它也會被排序。

以上是學習快速排序算法的詳細內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！