java - 在java中为对象数组列表实现归并排序

Question

我正在寻找使用对象数组列表来实现合并排序。理想情况下，我希望有一个静态方法，它将要排序的数组列表和一个布尔值作为参数。布尔值，如果为真，将递归实现归并排序，如果为假，将只使用循环而不是递归来实现排序。

这是用于对象数据的汽车类。

public class Car implements Comparable<Car> {
    private Double milesPerGallon;
    private String make;
    private String model;
    private Integer year;
    private Double milage;
    private Double initialPrice;

    public Car(Double milesPerGallon, String make, String model, Integer year, Double milage, Double initialPrice) {
       this.milesPerGallon = milesPerGallon;
       this.make = make;
       this.model = model;
       this.year = year;
       this.milage = milage;
       this.initialPrice = initialPrice;
    }

    @Override
    public int compareTo(Car o) {
        int result = this.year.compareTo(o.getYear());
        if (result == 0) {
            result = this.make.compareTo(o.getMake());
            if (result == 0) {
                return this.model.compareTo(o.getModel());
            } else {
                return result;
            }
        } else {
            return result;
        }
      }
}

我已经让递归部分按预期工作，但我遇到了迭代排序的问题。这是我的方法。

public static ArrayList<Car> mergeSort(ArrayList<Car> toSort, boolean recursive){

    // NON - RECURSIVE METHOD
    if(recursive == false){
        int currentSize;
        int leftStart;

        for(currentSize = 1; currentSize <= toSort.size() - 1; currentSize = 2 * currentSize){
            for(leftStart = 0; leftStart < toSort.size() - 1; leftStart += 2 * currentSize){
                int mid = Math.min(leftStart + currentSize - 1, toSort.size() - 1);

                int rightEnd = Math.min(leftStart + 2 * currentSize - 1, toSort.size() - 1);

                merge(toSort, leftStart, mid, rightEnd);
            }
        }
    }

    // RECURSIVE METHOD
    if(recursive == true){

        if(toSort == null){
            return toSort;
        }

        if(toSort.size() > 1){
            int mid = toSort.size() / 2;

            // split left half
            ArrayList<Car> left = new ArrayList<>();
            for(int i = 0; i < mid; i++){
                left.add(toSort.get(i));
            }

            // split right half
            ArrayList<Car> right = new ArrayList<>();
            for(int i = mid; i < toSort.size(); i++){
                right.add(toSort.get(i));
            }
            mergeSort(left, true);
            mergeSort(right, true);

            int i = 0; // index left
            int j = 0; // index right
            int k = 0; // index whole

            // merge left and right lists
            while(i < left.size() && j < right.size()){
                if(left.get(i).compareTo(right.get(j)) == -1){
                    toSort.set(k, left.get(i));
                    i++;
                }else{
                    toSort.set(k, right.get(j));
                    j++;
                }
                k++;
            }

            // remaining list elements
            while(i < left.size()){
                toSort.set(k, left.get(i));
                i++;
                k++;
            }
            while(j < right.size()){
                toSort.set(k, right.get(j));
                j++;
                k++;
            }
        }
    }


    return toSort;
}

这是迭代部分中使用的当前不起作用的方法。

public static void merge(ArrayList<Car> toSort, int left, int mid, int right){
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right- mid;

    // temporary lists
    ArrayList<Car> leftList = new ArrayList<>();
    ArrayList<Car> rightList = new ArrayList<>();

    // copy data to temporary lists
    for(i = 0; i < n1; i++){
        leftList.set(i, toSort.get(left + i));
    }
    for(j = 0; j < n2; j++){
        rightList.set(j, toSort.get(mid + left + j));
    }

    // merge temporary arrays into toSort
    i = 0;
    j = 0;
    k = mid;
    while(i < n1 && j < n2){
        if(leftList.get(i).compareTo(rightList.get(j)) == -1 || leftList.get(i).compareTo(rightList.get(j)) == 0){
            toSort.set(k, leftList.get(i));
            i++;
        }else{
            toSort.set(k, rightList.get(j));
            j++;
        }
        k++;
    }
    while(i < n1){
        toSort.set(k, leftList.get(i));
        i++;
        k++;
    }

标签： javasortingrecursionarraylistmergesort