我的QuickSort實現有什麼問題？

class PartitionIt 
{ 
     public static void partitionIt(int[] a, int l, int r, int pivot) 
    { 
    int i,j; 
    i = j = l+1; 

    while(j<= r) 
    { 
     if(a[j] <= a[pivot]) 
     { 
      swap(a,j,i); 
      i++; 
     } 
     j++; 
    } 
    swap(a,pivot,--i); 
} 

public static void swap(int[] a, int j, int i) 
{ 
    int temp = a[j]; 
    a[j] = a[i]; 
    a[i] = temp; 
} 

public static void displayArray(int[] a) 
{ 
    for(int i:a) 
     System.out.print(i+" "); 
    System.out.println(); 
} 

public static void QuickSort(int[] a, int l, int r) 
{ 
    if(r <= l) 
     return; 
    int pivot = getPivot(a,l,r); 
    partitionIt(a,l,r,pivot); 
    QuickSort(a,l,pivot); 
    QuickSort(a,pivot+1,r); 
} 

public static int getPivot(int[] a,int l,int r) 
{ 
    return l; 
} 

public static void main(String[] args) 
{ 

    int[] a = {3,2,8,5,1,4,7,6}; 
    int[] b = {1,2,3,4,5,6,7,8,9,0}; 
    int[] c = {5,4,2,4,7,6,5,3,2,1,10}; 

    displayArray(a); 
    System.out.println("After Parititon with pivot 3"); 
    QuickSort(a,0,a.length-1); 
    displayArray(a); 
    System.out.println(); 

    displayArray(b); 
    System.out.println("After Parititon with pivot 1"); 
    QuickSort(b,0,b.length-1); 
    displayArray(b); 
    System.out.println(); 

    displayArray(c); 
    System.out.println("After Parititon with pivot 5"); 
    QuickSort(c,0,c.length-1); 
    displayArray(c); 
    System.out.println(); 


}

}我的QuickSort實現有什麼問題？

3 2 8 5 1 4 7 6 
After Parititon with pivot 3 
1 2 3 4 5 6 7 8 

1 2 3 4 5 6 7 8 9 0 
After Parititon with pivot 1 
0 1 2 3 4 5 6 7 8 9 

5 4 2 4 7 6 5 3 2 1 10 
After Parititon with pivot 5 
1 2 2 4 3 4 5 5 6 7 10

它不是在後一種情況下正確排序。

任何人都可以在這裏幫忙。我被困住了這麼久。

在此先感謝！

來源

2014-10-27 shbolise

這是爲什麼？ 'if（a [j] <= a [pivot]）'你交換了相等的元素。 – 2014-10-27 10:56:45

這聽起來像是學習使用調試器的絕佳機會。在最後一個案例中查看代碼，然後親自查看出錯的地方。 – NPE 2014-10-27 10:58:40

感謝Marko。我現在明白了！ – shbolise 2014-10-27 11:02:16

在此片斷：

if(a[j] <= a[pivot]) 
     { 
      swap(a,j,i); 
      i++; 
     }

在 '< =' 應該是 '<'。

while the sequence were sorted to 1 2 2 4 3 4 5 5 7 6 10，pivot is'4'（left the one），while compare 4 < = 4，i ++，this cause the swap（a，樞軸， - i）將'4'（正確的位置）改變爲'4'（左邊的位置），而不是將'3'改變爲'4'。

來源

2014-10-27 12:05:22

我的QuickSort實現有什麼問題？

回答

相關問題