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 ++。