Java - 我的排序不起作用

Question

我创建了以下类来对字符串数组进行排序.

public class StringSort {
private String[] hotelNames;
private int arrayLength;

public void sortHotel(String[] hotelArray) {
    if (hotelArray.length <= 1) {
        return;
    }
    this.hotelNames = hotelArray;
    arrayLength = hotelArray.length;
    quicksort(0, arrayLength - 1);
}

private void quicksort(int low, int high) {
    int i = low, j = high;
    String first = hotelNames[low];
    String last = hotelNames[high];     
    String pivot = hotelNames[low + (high - low) / 2];

    while( (first.compareTo(last)) < 0 ) { // first is less than last
        while( (hotelNames[i].compareTo(pivot)) < 0 ) { // ith element is < pivot
            i++;
        }
        while( (hotelNames[j].compareTo(pivot)) > 0) { // jth element is > pivot
            j--;
        }
        if ( ( hotelNames[i].compareTo( hotelNames[j] )) <= 0 ) {
            swap(i, j);
            i++;
            j--;                
        }

        //recursive calls
        if (low < j) {
            quicksort(low, j);
        }
        if (i < high) {
            quicksort(i, high);
        }
    }
}

private void swap(int i, int j) {
    String temp = hotelNames[i];
    hotelNames[i] = hotelNames[j];
    hotelNames[j] = temp;
}

}

但是在我的主类(测试StringSort的类)中,当我这样做时:

StringSort str = new StringSort();
String[] hotel1 = {"zzzz", "wwww", "dddd", "bbbbb", "bbbba", "aaaf", "aaag", "zzz"};
str.sortHotel(hotel1);

然后我有另一个打印出数组的方法.但是当它打印出来时,它会按原样输出hotel1数组,不变.没有'排序'发生,我不知道我哪里出错了.

Answer 1

您实施快速排序有几个问题:

1. 第一个/最后一个比较 只要第一个元素小于最后一个元素,无论其他任何顺序如何,此代码都会使您的快速排序无法执行任何操作.

   while( (first.compareTo(last)) < 0 ) { // first is less than last
   

2. 交换前检查.这条线是不必要的:

   if ( ( hotelNames[i].compareTo( hotelNames[j] )) <= 0 ) {
   

你真正想要做的就是看看它i是否仍然小于j和保释.如果没有,那么交换.完成分区循环后,只要每个子数组中有两个以上的元素,就进行递归调用.