QuickSort算法天真的執行..但它爲什麼不工作？

Question

我對編程和java很新，所以請不要嘲笑:)。現在..我通過網絡查看QuickSort算法的正確實施，我意識到這一點。但我試圖以我能想到的無害，基本的方式來實現它。實際上是創建兩個單獨陣列（左，右），並繼續對它們進行排序等等...

這是代碼：

package excercise; 

public class MyQuickSort { 


    public static int list[] = {6,5,3,1,8,7,2,4}; 


    public static int[] addNumberToArray(int array[],int num){ 
     int newArray[] = new int[array.length+1]; 
     for(int i = 0;i<array.length;i++){ 
      newArray[i] = array[i]; 
     } 
     newArray[newArray.length-1] = num; 
     array = newArray; 
     return array; 
    } 


    public static int[] partition(int arr[]){ 

     while(arr.length>1){ 
      int pivotIndex = (int)(arr.length/2); 
      int left[] = new int[0]; 
      int right[] = new int[0]; 

      for(int i = 0;i<arr.length;i++){ 
       if(i==pivotIndex){ 
        continue; 
       } 

       else if(arr[i]<=arr[pivotIndex]){ 
        left = addNumberToArray(left,arr[i]); 
       } 
       else{ 
        right = addNumberToArray(right,arr[i]); 
       } 
      } 
      int origPivot = arr[pivotIndex]; 
      int k = 0; 
      while(k<left.length){ 
       arr[k] = left[k]; 
       k++; 
      } 
      arr[k] = origPivot; 
      k++; 
      while(k<arr.length){ 
       arr[k] = right[k-(left.length+1)]; 
      } 


      if(left.length>1){ 
      partition(left); 
      } 

      if(right.length>1){ 
      partition(right); 
      } 

     } 

      return arr; 
    } 




    public static void main(String[]args){ 
      list = partition(list); 
      for(int i = 0;i<list.length;i++){ 
       System.out.print(list[i]+" "); 
      } 

     } 
    } 

但爲什麼這是在一個循環中越來越棒，不工作？我不明白這段代碼有什麼問題。除了這個效率不高（至少可以說）！但我很固執，想要嘗試並使其工作。如果您有任何意見，它將會很棒！ THX提前

沒關係，這是新的代碼，調試一切似乎都正常工作後，但是當我要打印的新整理改編，它仍然打印我的原始排序的數組。遞歸將整個事情轉回到它開始的地方。我怎樣才能讓它「保存步驟」？我應該在哪裏放置「返回」電話，我應該返回什麼？

public class MyQuickSort { 

    public static int list[] = {6,5,3,1,8,7,2,4}; 
    public static boolean sorted; 
    public static int[] addNumberToArray(int arr[],int num){ 
     int newArr[] = new int[arr.length+1]; 
     for(int i = 0;i<arr.length;i++){ 
      newArr[i] = arr[i]; 
     } 
     newArr[newArr.length-1] = num; 
     arr = newArr; 
     return arr; 

    } 


    public static void partition(int arr[]){ 

     while(!sorted){ 
      int pivotIndex = (int)(arr.length/2); 
      int left[] = new int[0]; 
      int right[] = new int[0]; 

      for(int i = 0;i<arr.length;i++){ 
       if(i==pivotIndex){ 
        continue; 
       } 
       else if(arr[i]<=arr[pivotIndex]){ 
        left = addNumberToArray(left,arr[i]); 
       } 
       else{ 
        right = addNumberToArray(right,arr[i]); 
       } 
      } 
      int origPivot = arr[pivotIndex]; 
      int k = 0; 
      while(k<left.length){ 
       arr[k] = left[k]; 
       k++; 
      } 
      arr[k] = origPivot; 
      k++; 
      while(k<arr.length){ 
       arr[k] = right[arr.length-arr.length-(left.length+1)+k]; 
       k++; 
      } 


      if(left.length>1){ 
       partition(left); 
      } 


      if(right.length>1){ 
       partition(right); 
      } 

      if(left.length<=1&&right.length<=1){ 
       sorted = true; 

      } 

     } 



    } 








    public static void main(String[] args) { 
     partition(list); 
     for(int i = 0;i<list.length;i++){ 
      System.out.print(list[i]+" "); 
     } 


    } 

} 

Answer 1

你的算法陷在這個循環中

while(k<arr.length){ 
    arr[k] = right[k-(left.length+1)]; 
} 

的原因是，你不增加說明您的K。

嘗試

while(k<arr.length){ 
    arr[k] = right[k-(left.length+1)]; 
    k++; 
} 

Answer 2

酷！你的實現似乎邏輯上描述了快速排序。但是，請注意，快速排序不能使用其他緩衝區來實現。它應該在它自己的主數組中進行排序，遞歸調用只傳遞開始和結束邊界。你的實現更多的是使用快速排序邏輯的mergesort風格。是的，你錯過了上述評論者所述的k ++。