java归并排序从最大到最小

Question

这个类从最小到最大的数字排序，如何进行相反的排序(从最大到最小)。

我尝试更改 divide() 和 merger() 中的一些字符，但这会导致停止工作。

    public void divide(int startIndex, int endIndex) {
        // Divide till you breakdown your list to single element
        if (startIndex < endIndex && (endIndex - startIndex) >= 1) {
            int mid = (endIndex + startIndex) / 2;
            divide(startIndex, mid);
            divide(mid + 1, endIndex);        

            //merging Sorted array produce above into one sorted array
            merger(startIndex, mid, endIndex);            
        }       
    }   

    public void merger(int startIndex, int midIndex, int endIndex) {
        // Below is the merged array that will be sorted array Array[i - midIndex], Array[(midIndex + 1) - endIndex]
        ArrayList<Integer> mergedSortedArray = new ArrayList<Integer>();

        int leftIndex = startIndex;
        int rightIndex = midIndex + 1;

        while (leftIndex <= midIndex && rightIndex <= endIndex) {
            if (inputArray.get(leftIndex) <= inputArray.get(rightIndex)) {
                mergedSortedArray.add(inputArray.get(leftIndex));
                leftIndex++;
            } else {
                mergedSortedArray.add(inputArray.get(rightIndex));
                rightIndex++;
            }
        }       

        // Either of below while loop will execute
        while (leftIndex <= midIndex) {
            mergedSortedArray.add(inputArray.get(leftIndex));
            leftIndex++;
        }

        while (rightIndex <= endIndex) {
            mergedSortedArray.add(inputArray.get(rightIndex));
            rightIndex++;
        }

        int i = 0;
        int j = startIndex;
        // Setting sorted array to original one
        while (i < mergedSortedArray.size()) {
            inputArray.set(j, mergedSortedArray.get(i++));
            j++;
        }
    }
}

Answer 1

您需要更改定义结果顺序的“比较操作”:

if(inputArray.get(leftIndex) <= inputArray.get(rightIndex)) {

按升序对项目进行排序。为了(双关语)得到相反的结果，改变值的比较方式；相反的是:

if(inputArray.get(leftIndex) > inputArray.get(rightIndex)) {

如果您想让算法更加模块化，您可以更改其接口(interface)以接受 Comparator<T>然后用于比较值的实例，例如

public void merger(
        int startIndex,
        int midIndex,
        int endIndex,
        Comparator<Integer> comparator) {
    // ...
    if(comparator.compare(inputArray.get(leftIndex), inputArray.get(rightIndex)) < 0) {
    // ...
}

然后调用例如:

merger(start, mid, end, Integer::compareTo); // or even:
merger(start, mid, end, Comparator.naturalOrder());

用于上升；或

Comparator<Integer> comparator = Integer::compareTo;
merger(start, mid, end, comparator.reversed());
// or as one-liner:
merger(start, mid, end, Collections.reverseOrder(Integer::compareTo)); // or even:
merger(start, mid, end, Comparator.reverseOrder());

按降序排列结果。