从右到左插入排序

Question

我正在尝试学习 Java 中的插入排序，但我遇到了问题。我按升序学习了插入排序。现在，我需要按降序排列，但我必须开始从右到左对数组进行排序。

public class Sorting {

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 1; i < N; i++) {                            
        for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
            swap(a, j, j - 1);
    }
}

private static void swap(Comparable[] a, int i, int j) { 
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
}

private static boolean less(Comparable v, Comparable w) {                                                   
    return v.compareTo(w) < 0;
}

}

上面的代码将数组从左到右按升序（1,2,3,4,..）排序。

我需要按降序更改它，但从右到左排序 (5,4,3,2..)。我更改了代码并尝试了这个：

    public static void sort(Comparable[] a) { 
    int N = a.length;
    for (int i = N-1; i>=0; i--) { 
        for (int j = i; j >= 1 && less(a[j-1], a[j]); j++)
            swap(a, j, j-1);
    }
}

我多次更改排序方法，但出现错误..

Answer 1

使用相同的算法，只是在较小的检查中，交换方法 less 的参数，使得：less(a[j - 1], a[j])。然后较小的元素将向右移动。

Answer 2

这里我也测试了一下，试试看：

    public class InsertionSort {
        public static void main(String[] args) {
            Comparable[] a = new Comparable[]{5,6,12,1,3,15,4,0,9};
            sort(a);
            for (int i = 1 ; i < a.length; i++)
                assert a[i].compareTo(a[i-1]) >= 0;
            System.out.println("sort is correct");
        }

        public static void sort(Comparable[] a) { // Sort a[] into         increasing order.
            int N = a.length;
            for (int i = N - 1; i > 0; i--) { // Insert a[i] among         a[i-1], a[i-2],a[i-3]... ..                               
                for (int j = i; j < N && less(a[j - 1], a[j]); j++)
                    exch(a, j, j - 1);
            }
        }

        private static void exch(Comparable[] a, int i, int j) { 
            Comparable t = a[i];
            a[i] = a[j];
            a[j] = t;
        }

                private static boolean less(Comparable v, Comparable w)                 {                                                   
            return v.compareTo(w) < 0;
        }

    }

从右到左插入排序

Insertion Sort from Right to Left

java

sorting

insertion-sort