學習快速排序演算法

快速排序是最有效的演算法之一，它使用分治技術對陣列進行排序。

快速排序的工作原理

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

當:

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

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中文網其他相關文章！