使用第一個元素作爲支點快速排序

Question

我通過選擇第一個元素作爲支點，實現了快速排序。它適用於一般的測試用例，但考慮一個例子，當數組被反向排序時，例如5 4 3 2 1.我知道它在哪裏拋出運行時錯誤。但我無法正確解決它。第一個元素的實現是否正確？請提出修改建議。

public static void quicksort(int low,int high) 
    { 

    if(low<high) 
    { 
    int temp=0; 
    int pivot=a[low];      
    int large_index=low+1; 
    int small_index=high; 

    while(large_index<=small_index) 
    { 
     while(a[small_index]>pivot) 
     small_index--; 

     while(a[large_index]<pivot) 
     large_index++; 

     if(large_index<=small_index) 
     { 
     temp = a[large_index]; 
     a[large_index]= a[small_index]; 
     a[small_index]= temp; 
     large_index++; 
     small_index--; 
     } 
    } 

    temp = a[small_index]; 
    a[small_index]= a[low]; 
    a[low]= temp; 


    quicksort(low,small_index-1); 
    quicksort(small_index+1,high); 
    } 

    } 

Answer 1

下循環繼續上面high，當large_index已經開始在樞軸上方，它發生樞軸小於位於後它的每一個元素較大：

while(a[large_index]<pivot) 
large_index++; 

可能有其他錯誤，當然。

Answer 2

有多個缺陷：

a）所述環的外側不必要的交換

溫度= A [small_index]; a [small_index] = a [低]; a [低] =臨時;

b）large_index的錯誤初始化。

c）在不檢查 small_index和large_index的值的情況下調用遞歸函數。

我已經糾正他們，

現在的功能將類似於：

if (low < high) { 
      int temp = 0; 
      int pivot = a[low]; 
      int large_index = low; 
      int small_index = high; 

      while (large_index <= small_index) { 
       while (a[small_index] > pivot) 
        small_index--; 

       while (a[large_index] < pivot) 
        large_index++; 

       if (large_index <= small_index) { 
        temp = a[large_index]; 
        a[large_index] = a[small_index]; 
        a[small_index] = temp; 
        large_index++; 
        small_index--; 
       } 
      } 

      if(low < small_index) 
      { 
       quicksort(low, small_index); 
      } 
      if(large_index < high) 
      { 
       quicksort(large_index, high); 
      } 
     } 

現在，看在你的代碼中的變量：（代碼將在最後一次迭代失敗任何給定的輸入，除非輸入不排序）

考慮輸入2,1

1st iteration: 

pivot = 2 
large_index = 1; 
small_index = 1; 


while1: 
1<=1 -> true 
    while2: 1>2 false. 
    while3: 1<2 true. -> large_index++ 
       2nd time in while loop large_index =2 which is > the size of a. 

產生IndexArrayOutOfBounds。

這說明你的初始化large_index是錯誤的。

它應該是：large_index = low;而不是低+ 1;

希望這會有所幫助。

Answer 3

經過一番嘗試後，我能夠使Quicksort功能，現在它工作正常。 @BatScream我仍然在我的代碼中使用small_index = low + 1。所以這不是我猜的錯誤。原始的快速排序算法遵循這種機制。請參考Princeton Professor Robert Sedgewick在QuickSort上的演講。請注意，如果編輯過的快速排序算法存在缺陷。

public static void quicksort(int low,int high) 
{ 

    if(low<high) 
    { 
    int temp=0; 
    int pivot=a[low];      
    int large_index=low+1; 
    int small_index=high; 

    while(large_index<small_index) 
    { 

    while(a[large_index]<pivot) { 
    if(large_index==high) 
    break; 
    large_index++; 
    } 

    while(a[small_index]>pivot) 
    { 
    if(small_index==low) 
    break; 
    small_index--; 
    } 

    if(large_index<small_index) { 
    temp = a[large_index]; 
    a[large_index]= a[small_index]; 
    a[small_index]= temp; 
    large_index++; 
    small_index--; 
    } 
    } 

    if(a[small_index]<pivot) {        
     temp = a[small_index]; 
     a[small_index]= a[low]; 
     a[low]= temp; 
    } 

    if(low<small_index)         //Recursively sort the left half. 
    { 
    quicksort(low,small_index-1); 
    } 

    if(high>small_index)         //Recursively sort the right half. 
    { 
    quicksort(small_index+1,high); 
    } 
    } 

    }