快速排序的解釋

我正在研究快速排序，我發現算法解釋here 快速排序的解釋

最好到我的理解，但我在臺階的一個有一個問題。

可能有人解釋我的正常會是什麼，直到樞軸的步驟保持其右側放置，如果在圖像中顯示在這一點上，數是？

我認爲這將是更有益的，如果讀者首先看到的步驟在幻燈片中解釋，我發現那裏是說明快速排序算法很多其他不同的方法。

Editted： 我猜到最終測序將會像

24 49 16 38 55 21 36 9 * 7 * 57 81 85 63 79 74 85 97 61 77 70 * 68。（由空指針提到的）

難道停止流動的藍色發現68右側的最大元素和跳過檢查較小的元素爲藍色的指數衝過/見了紅指數？

來源

2015-12-02 OnePunchMan

你跳過7藍色，並停止在7紅色，正確的一個元素比'76'' – BeyelerStudios

分區步驟的目的是確定所有小元素都放在大元素的左側。小/大分類是通過與「數據透視」值比較來決定的。對於算法的進展，必須確保至少有一個小的元素和一個大的元素。 –

@YvesDaoust正如你所提到的那樣，應該有一個小的**和一個大的（需要兩個數字），在上面的情況下流程會是什麼，因爲只剩下一個要比較的元素。 – OnePunchMan

繼續.. [*藍色指針; **紅色指針; ***空置] 樞軸= 57

=> 24 49 16 38 55 21 36 *68 7 **9 81 85 63 79 74 85 97 61 77 70 *** 

=> 24 49 16 38 55 21 36 *9 7 **68 81 85 63 79 74 85 97 61 77 70 ***

我期望的那樣，他們是因爲它是東西，直到這將是明顯的。 9和68交換。現在右端小於57的下一個數字是7（所以**），大於它的數字是68（so *）。

=> 24 49 16 38 55 21 36 9 **7 *68 81 85 63 79 74 85 97 61 77 70 ***

但由於索引將不進一步滿足條件，因此與紅色指針68的數量將被移動到空閒空間和57到其處於中間位置。因此，順序應該是：

=> 24 49 16 38 55 21 36 9 **7 *57 81 85 63 79 74 85 97 61 77 70 ***68

來源

2015-12-02 12:20:19 nullpointer

你能否像我在幻燈片中解釋過的那樣解釋我？我猜想順序會是這樣的，但是怎麼樣？ – OnePunchMan

@Tootsie_Roll編輯答案...雖然沒有圖表，但試圖提供更好的視覺 – nullpointer

在你的流程中，你首先嚐試找到更小的元素。首先找到較小的元素還是較大的元素優先？ – OnePunchMan

快速排序的變化：一個換號碼後

void swap(int *i, int *j) 
{ 
    int t = *i; 
    *i = *j; 
    *j = t; 
} 

void QuickSort(int a[], int lo, int hi) { 
    int i = lo, j = (lo + hi)/2, k = hi; 
    int pivot; 
    if (a[k] < a[i])   // median of 3 
     swap(a+k, a+i); 
    if (a[j] < a[i]) 
     swap(a+j, a+i); 
    if (a[k] < a[j]) 
     swap(a+k, a+j); 
    pivot = a[j]; 
    showa(lo, hi); 
    while (i <= k) {   // partition 
     while (a[i] < pivot) 
      i++; 
     while (a[k] > pivot) 
      k--; 
     if (i <= k) { 
      swap(a+i, a+k); 
      i++; 
      k--; 
      showa(lo, hi); 
     } 
    } 
    if (lo < k)     // recurse 
     QuickSort(a, lo, k); 
    if (i < hi) 
     QuickSort(a, i, hi); 
}

輸出，用 '*'：

57 70 97 38 63 21 85 68 76 9 81 36 55 79 74 85 16 61 77 49 24 
24*70 97 38 63 21 85 68 76 9 57*36 55 79 74 85 16 61 77 49 81* 
24 49*97 38 63 21 85 68 76 9 57 36 55 79 74 85 16 61 77 70*81 
24 49 16*38 63 21 85 68 76 9 57 36 55 79 74 85 97*61 77 70 81 
24 49 16 38 55*21 85 68 76 9 57 36 63*79 74 85 97 61 77 70 81 
24 49 16 38 55 21 36*68 76 9 57 85*63 79 74 85 97 61 77 70 81 
24 49 16 38 55 21 36 57*76 9 68*85 63 79 74 85 97 61 77 70 81 
24 49 16 38 55 21 36 57 9*76*68 85 63 79 74 85 97 61 77 70 81 
9*49 16 38 24*21 36 57 55*          
9 21*16 38 24 49*36 57 55          
9 21 16 24*38*49 36 57 55          
9 21 16 24              
9 16*21*24              
9 16               
9 16               
     21 24              
     21 24              
      36*49 38*57 55          
      36 38*49*57 55          
      36 38            
      36 38            
        49 55*57*          
        49 55 57          
          74*68 85 63 79 76*85 97 61 77 70 81 
          74 68 70*63 79 76 85 97 61 77 85*81 
          74 68 70 63 61*76 85 97 79*77 85 81 
          74 68 70 63 61 76 85 97 79 77 85 81 
          61*68 70 63 74*      
          61 68 63*70*74      
          61 63*68*       
          61 63 68        
            70 74      
            70 74      
              79*97 81*77 85 85* 
              79 77*81 97*85 85 
              79 77 81 97 85 85 
              77*79*    
              77 79    
                 85*85 97* 
                 85 85 97 
                 85 97 
                 85 97 
9 16 21 24 36 38 49 55 57 61 63 68 70 74 76 77 79 81 85 85 97

來源

2015-12-02 13:58:53 rcgldr

快速排序的解釋

回答

相關問題