java - 虽然我实现的快速排序方法适用于整数和字符串数组，但此方法不适用于汽车数组

Question

我尝试实现三个对象的快速排序:Integer、String 和 Cars。当我尝试运行快速排序代码时，快速排序方法适用于整数和字符串数组，但不适用于汽车数组。汽车类由两个参数变量组成:品牌名称(String)和型号年份(int)。以下是用于快速排序的代码。

public class SortArray
{
    private static <T extends Comparable <? super T>> int partition(T[] a, int first, int last)
    {
        int indexFromLeft = first;
        int indexFromRight = last;
        while(indexFromRight - indexFromLeft >= 1)
        {
            T pivotValue = a[first + (last - first) / 2];
            while(a[indexFromLeft].compareTo(pivotValue) < 0)
            {
                indexFromLeft++;
            }
            while(pivotValue.compareTo(a[indexFromRight]) < 0)
            {
                indexFromRight--;
            }
            if(indexFromLeft < indexFromRight)
            {
                T temp = a[indexFromLeft];
                a[indexFromLeft] = a[indexFromRight];
                a[indexFromRight] = temp;
                indexFromLeft++;
                indexFromRight--;
            }
        }
        return indexFromLeft;
    }
    public static <T extends Comparable<? super T>> void quickSortRecursively(T[] a, int first, int last)
    {
        if(first < last)
        {
            int pivot = partition(a, first, last);
            quickSortRecursively(a, first, pivot - 1);
            quickSortRecursively(a, pivot + 1, last);
        }
    }
    public static <T extends Comparable<? super T>> void quickSort(T[] data)
    {
        if(data == null || data.length == 0)
        {
             return;
        }
        quickSortRecursively(data, 0, data.length - 1);
    }
    public static <T> void display(T[] printedArray)
    {
        int index;
        for(index = 0; index < printedArray.length - 1; index++)
        {
            System.out.print(printedArray[index] + ", ");
        }
        System.out.println(printedArray[index]);
    }
}

这是我在主类中用来演示快速排序的代码。

public class MainSort
{
    public static void main(String[] args)
    {
        Cars[] list3 = new Cars[8];
        list3[0] = new Cars("Mazda", 2004);
        list3[1] = new Cars("BMW", 1996);
        list3[2] = new Cars("Jaguar", 1989);
        list3[3] = new Cars("Tesla", 2017);
        list3[4] = new Cars("Acura", 2008);
        list3[5] = new Cars("Chrysler", 2012);
        list3[6] = new Cars("Volvo", 2001);
        list3[7] = new Cars("Pontiac", 1983);
        System.out.println("\nOriginal Array of Cars:");
        SortArray.display(list3);
        SortArray.quickSort(list3);
        SortArray.display(list3);
    }
}

顺便说一句，我也提供汽车类别。

public class Cars implements Comparable
{
    private String name;
    private int year;
    public Cars()
    {
        name = " ";
        year = 0;
    }
    public Cars(String brandName, int modelYear)
    {
        name = brandName;
        year = modelYear;
    }
    public String getName()
    {
        return name;
    }
    public int getYear()
    {
        return year;
    }
    public String toString()
    {
        return name + " " + year;
    }
    @Override;
    public int compareTo(Object[] t)
    {
        Cars c = (Cars) t;
        int y = c.getYear();
        if(year <= y)
        {
            return -1;
        }
        else
        {
            return 1;
        }
    }
}

当我尝试运行代码时，我在以下几行中发现了“线程“main”java.lang.ArrayIndexOutOfBoundsException: 8”中的异常:

while(a[indexFromLeft].compareTo(pivotValue) < 0)

在分区方法中，

int pivot = partition(a, first, last);

在快速排序递归方法中，

quickSortRecursively(data, 0, data.length - 1);

在快速排序方法中，并且

SortArray.quickSort(list3);

在主类中。

我希望快速排序方法能够很好地处理 Car 类的数组以及 Integer 和 String。

Answer 1

两个问题:

1. 您仅根据车型年份进行排序，这可能是也可能不是问题
2. 您的 compareTo() 方法不满足所需的契约(Contract)。当两辆车具有相同的排序键(在您的情况下是车型年份)时，它必须返回零，但事实并非如此。在某些情况下，主元值将与其自身进行比较，并且会返回错误的结果，从而破坏排序。