快速排序幫助 - 分區

Question

我正在迭代實現自己的快速排序和遞歸。

它獲得第一個分區罰款，其中樞軸右側的數字大於和左側小於。

但是，我的分區似乎沒有劃分右側，只有左側。

int[] data = {3,5,2,7,11,9,1,88,22}; 

public void qSort(int[] data, int left, int right){ 
    int pivot = partition(data,left,right); 
    pivot = partition(data,pivot,data.length-1); // Test example for right side only 
} 

public int partition(int[] data, int left, int right){ 
    int pivot = left; 
    left++; 

    while (left <= right){ 
     while ((left <= right) && (data[left] <= data[pivot])) { 
      left++; 
     } 

     while ((left <= right) && (data[right] >= data[pivot])){ 
      right--; 
     } 

     if (left < right){ 
      int temp = data[left]; 
      data[left] = data[right]; 
      data[right] = temp; 
      left++; 
      right--; 
     }   
    } 

    if (data[right] < data[pivot]){ 
     int temp = data[right]; 
     data[right] = data[pivot]; 
     data[pivot] = temp; 
     pivot = right; 
    } 

    return pivot; 
} 

任何幫助，將不勝感激，我難倒:(

Answer 1

其實你的分區執行工作正常，你傳遞了錯誤的left參數partition：

pivot = partition(data, pivot, data.length - 1); // Test example for right side only 

它應該是：

pivot = partition(data, pivot + 1, data.length - 1); // You need to exclude the pivot itself. 

因爲在您的實施中，您選擇最左邊的元素作爲數據透視表，因此如果您在嘗試分割正確部分時通過作爲left參數，則所有內容都將保持不變，因爲它已被分區。