快速排序是最有效的演算法之一，它使用分治技術(shù)對(duì)陣列進(jìn)行排序。

快速排序的工作原理

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

當(dāng):

時(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ù)組的開(kāi)頭但不是最小的數(shù)字，則快速排序確定需要移動(dòng) 5 步才能為數(shù)組中的 5 個(gè)較小元素騰出空間 - 假設(shè)有 5 個(gè)這樣的元素?cái)?shù)字。

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

此時(shí)：

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

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

在下一個(gè)索引處，值為 6，小於 10。快速排序 將步數(shù)增加到 2，因?yàn)橹髟F(xiàn)在需要為兩個(gè)較小的數(shù)字騰出空間：4 和 6 .

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

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

numberOfStepsToMove 不會(huì)改變 23 或 40，因?yàn)檫@兩個(gè)值都大於基準(zhǔn)值，且在陣列中不應(yīng)位於基準(zhǔn)值之前：

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

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

現(xiàn)在我們已經(jīng)到達(dá)了數(shù)組的末尾，我們知道有 5 個(gè)數(shù)字小於 10。因此，主元 (10) 必須向前移動(dòng) 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)在我們有了一個(gè)函數(shù)來(lái)幫助我們找到放置樞軸的位置，讓我們看看 Qucik Sort 如何將數(shù)組劃分為更小的數(shù)組，並利用 getNumberOfStepsToMove 函數(shù)來(lái)放置所有數(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ù)組，確保透過(guò)將元素與主元進(jìn)行比較來(lái)對(duì)元素進(jìn)行排序。

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

• 演算法遞歸地對(duì)包含小於主元的元素的左子數(shù)組進(jìn)行排序。
• 當(dāng)子數(shù)組有一個(gè)或零個(gè)元素時(shí)，遞歸停止，因?yàn)樗呀?jīng)排序。

現(xiàn)在我們需要對(duì)陣列的右邊執(zhí)行相同的過(guò)程：

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

在此範(fàn)例中，右側(cè)已經(jīng)排序，但演算法不知道這一點(diǎn)，如果沒(méi)有排序，它也會(huì)被排序。

以上是學(xué)習(xí)快速排序演算法的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！