Java实现插入排序(代码有点繁琐,但很好理解)

发布于 2021-07-29  41 次阅读


插入排序就像整理扑克牌,一张一张牌往后移,然后插入到合适的位置。

package com.apesblog.sort.insertion;

public class Insertion {

    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (greater(a[i - 1], a[i])) {
                Comparable t = a[i];
                int j = i - 1;
                while (j >= 0 && greater(a[j], t)) {
                    a[j + 1] = a[j];
                    j--;
                }
                //结束while时,j会多减一次
                j++;
                a[j] = t;
            }
        }
    }

    private static boolean greater(Comparable i, Comparable j) {
        return i.compareTo(j) > 0;

    }

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

}
package com.apesblog.sort.insertion;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        Integer[] a = { 4, 5, 6, 3, 2, 1 };
        Insertion.sort(a);
        System.out.println("插入排序:" + Arrays.toString(a));
        
        String[] str = { "d", "e", "f", "c", "b", "a" };
        Insertion.sort(str);
        System.out.println("插入排序:" + Arrays.toString(str));

    }

}