java - 快速排序 Java

Question

您好，我目前正在努力让我的快速排序程序正常工作，但无法弄清楚我哪里出错了，我花了几个小时试图找出为什么它不起作用但运气不好，当我运行我的代码时没有任何反应.我还有其他四种以类似方式工作的排序算法，这是最让我困惑的。下面是我的快速排序程序代码

import java.io.IOException;

public class QuickSort  {



public static int[] compute(int[] array, int lower, int higher )throws IOException{

    if(lower<higher){
        int pivot=split(array,lower,higher);
        if(pivot>1)
            compute(array, lower, pivot-1);

        if(pivot+1<higher)
            compute(array, pivot+1, higher);


    }

    return array;

}


public static int split(int[] array, int lower, int higher){

    while(true){
        int pivot=array[lower];

        while(array[lower]<pivot)
            lower++;

        while(array[higher]>pivot)
            higher--;


        if(lower<higher){

            int temp=array[higher];
            array[higher]=array[lower];
            array[lower]=temp;
        }
        else{
        return higher;
    }
    }
}

这是我运行代码的测试类:

import java.io.IOException;
import java.util.Scanner;


public class Test extends ReadIn{ 

static BubbleSort bubble=new BubbleSort();


  public static void main(String[] args) throws IOException{
  System.out.println("Enter 1 for BubbleSort\nEnter 2 for Insertion Sort\nEnter 3      for Selection Sort\nEnter 4 for Merge Sort\nEnter 5 for QuickSort\nPlease input sorting algorithm to use for sorting:");
  Scanner input=new Scanner(System.in);
  int number=input.nextInt();
  final long startTime = System.currentTimeMillis();
  int[] Array=read();

  if(number==1){
      Array=BubbleSort.compute(Array);
        for(int i=0;i<BubbleSort.compute(Array).length;i++){
      System.out.println(Array[i]);

    }

  }
  if(number==2){
      Array=InsertionSort.compute(Array);
        for(int i=0;i<InsertionSort.compute(Array).length;i++){
      System.out.println(Array[i]);

    }

  }
  if(number==3){
      Array=SelectionSort.compute(Array);
        for(int i=0;i<SelectionSort.compute(Array).length;i++){
      System.out.println(Array[i]);

    }

  }
  if(number==4){
      Array=MergeSort.compute(Array);
        for(int i=0;i<MergeSort.compute(Array).length;i++){
      System.out.println(Array[i]);

    }

  }
  if(number==5){
  Array=QuickSort.compute(Array,0,Array.length-1);
        for(int i=0;i<QuickSort.compute(Array,0,Array.length-1).length;i++){
      System.out.print(Array[i]);

    }

  }


    final long endTime = System.currentTimeMillis();
    System.out.println("Total execution time: " + (endTime - startTime) );
}





}

当我按 5 时没有任何反应，其余的工作正常。我无法弄清楚问题出在哪里，因此我们将不胜感激。

Answer 1

如果输入中有重复的数字，您的快速排序代码将永远循环，因为数字可以一直相互交换。如评论中所述，您应该使用示例数组手动尝试代码，或检查使用 debugger 运行的代码.请参阅下面的示例数组。

您可能希望将 while(true) 循环切换为递归调用以使代码更清晰一些。此外，您可以在我的 Quicksort online tutorial 上练习快速排序的不同步骤。 .

假设数组 = {3,1,2,3}，基准值为 3。什么都不会改变，代码将永远循环。

while(true){
    int pivot=array[lower];

    while(array[lower]<pivot)
        lower++;

    while(array[higher]>pivot)
        higher--;


    if(lower<higher){   //this will just swap the 3's with each other. 
        int temp=array[higher];
        array[higher]=array[lower];  
        array[lower]=temp;
    }
    else{
      return higher;
    }
}