如何理解或解釋在Quicksort中第一次調用分區？

Question

這涵蓋了來自https://stackoverflow.com/help/on-topic的「軟件算法」，或者在這種情況下，用於對一組數字進行排序的快速排序算法。

這是我現在用的是快速排序算法代碼（開裂編碼採訪第五版）

static void quickSort(int[] arr, int left, int right) { 
    int index = partition(arr, left, right); 
    if(left < index - 1) { 
     //sort left half 
     quickSort(arr, left, index - 1); 
    } 
    if(index < right) { 
     //sort right half 
     quickSort(arr, index, right); 
    } 
} 
static int partition(int[] arr, int left, int right) { 
    int pivot = arr[ (left + right)/2]; 
    while(left <= right) { 
     while(arr[left] < pivot) { 
      left ++; 
     } 
     while(arr[right] > pivot) { 
      right --; 
     } 
     if(left <= right) { 
      swap(arr, left, right); 
      left ++; 
      right --; 
     } 
    } 
    return left; 
} 
static void swap(int arr[], int one, int two) { 
    int temp = arr[one]; 
    arr[one] = arr[two]; 
    arr[two] = temp; 
} 

我知道快速排序算法的總結是讓所有小於樞軸的元素出現在左邊的樞軸和大於樞軸的所有元件都在樞軸的右側。順便說一下，是否存在與樞軸相同的元素應該去哪裏的規則？

所以我的試運行是從https://www.hackerrank.com/challenges/angry-children

{10, 100, 300, 200, 1000, 20, 30} 

這個排序的數組後第一個電話進行分區，這是我選擇了基於該算法的我的數組

[10, 100, 30, 20, 1000, 200, 300] 

樞軸的狀態是200的值。然而在第一次通話之後，我不知道如何理解這一點，因爲200左邊的所有東西都不小於200（1000）。我知道這個算法是有效的，因爲我得到了最終結果排序數組。

有人可以幫我解釋第一次調用分區的結果嗎？

Answer 1

我覺得我的困惑是quicksort的整個想法。如果其他人正在努力，那麼現在就來解釋一下。

int index = partition(arr, left, right); 

 ＆NBSP＆NBSP＆nbspWill分區與問候到樞軸，這將是在這種情況下的索引陣列。確保左側的所有內容都小於pivot，而右側的所有內容都大於pivot。

現在，如果我們看一下這個代碼

if(left < index - 1) { 
    quickSort(arr, left, index - 1); 
} 

基本上是問有沒有什麼樞軸的左邊？如果存在，則將所有內容排列在數據透視的左側。請注意，如果left = index - 1，則此測試不會通過，或者在數據透視的左側只有一個元素。沒有必要排序。

及其與此代碼段完全相同的邏輯，以及（適用於樞軸的右側）

if(index < right) { 
     //sort right half 
     quickSort(arr, index, right); 
    } 

Answer 2

現在看起來很合理。 這個分區對於與pivot元素相同的元素（包括pivot元素本身）可能會有點奇怪，它可以將這些元素扔到左右任何一個子數組中，但它仍然可以使左子數組中的元素少於pivot或equal值，或等於右側子數組，並返回右側子數組中第一個元素的索引。儘管如此，它可能並不妨礙算法的工作，因爲它只是在處理子陣列時將這些元素移動到中間位置。

真的沒有那麼錯。如果分區將所有相等的元素移動到其中一個子數組，那麼當由於副本移動到一邊導致子數組大小不匹配而導致許多重複元素時，它將導致性能低下。

也有所謂的3路分區，它比通常的分區稍微複雜一點，但處理重複更合理的方式。