插入排序

最坏情况下需要~N²/2次比较和~N²/2次交换。

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.List;

public class Insertion<T extends Comparable> {

    private static <T extends Comparable> boolean less(T a, T b) {
        return a.compareTo(b) == -1;
    }

    private static <T> void exch(T[] a, int lo, int j) {
        T tmp = a[lo];
        a[lo] = a[j];
        a[j] = tmp;
    }

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

    public static <T extends Comparable> List<T> sort(Class<T> clazz, List<T> list) {
        T[] arr = (T[]) Array.newInstance(clazz, list.size());
        list.toArray(arr);
        sort(arr);
        list = Arrays.asList(arr);
        return list;
    }

    public static void main(String[] args) {
        Integer[] arr = {5,4,6,3,7,2,8,1,9,0};

        //测试数组
        Insertion.sort(arr);
        System.out.print(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            System.out.printf(", %d", arr[i]);
        }
        System.out.println();

        //测试列表
        List list = Arrays.asList(5,4,6,3,7,2,8,1,9,0);
        list = Insertion.sort(Integer.class, list);
        System.out.print(list.get(0));
        for (int i = 1; i < arr.length; i++) {
            System.out.printf(", %d", list.get(i));
        }
        System.out.println();
    }

}