快速排序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 BubbleSortnEnter 2 for Insertion SortnEnter 3      for Selection SortnEnter 4 for Merge SortnEnter 5 for QuickSortnPlease 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

如果输入中有重复的数字，您的快速排序代码将永远循环，因为这些数字可以不断交换。如注释中所述，您应该使用示例数组手动试用代码，或者使用调试器检查运行的代码。请参阅下面的示例数组。

您可能希望将while(true)循环切换为递归调用，以使代码更加清晰。此外，您可以在我的快速排序在线教程中练习快速排序的不同步骤。

假设数组=｛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;
    }
}

Answer 2

虽然你的程序看起来什么都没做，但它可能只是在这个循环中无限循环：

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;
        // I recommend adding this line for you to see what's going on
        System.out.println("lower="+lower+", higher="+higher+", pivot="+pivot);
    }
    else{
        return higher;
    }
}

例如，如果您的数组中有相等的值，比如值65存在两次，那么循环将永远运行。。。

int[] Array={1,41,2,90,32,65,12,43,78,65,46,67};

此外，在上面的循环中，我添加了一个更高、更低和枢轴值的额外打印输出，这将帮助您了解在这个狡猾的循环中发生了什么。

一般来说，编写while（true）循环不是一个好的做法，因为很容易将系统挂在上面