插入排序，假设第一个元素排好，之后的元素对排好的部分从后向前比较并逐一移动。

插入排序与选择排序一样，当前索引左边的所有元素都是有序的，但是它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。

插入排序所需的时间取决于输入中元素的初始顺序。对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的顺组或是逆序数组进行排序要快得多。

• java实现

public class Insertion {
    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--) {
                exch(a, j, j - 1);
            }
        }
    }

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

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

    public static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }
        System.out.println();
    }

    public static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String[] a = {"4", "3", "6", "1"};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

• python实现

class Insertion:
    def sort(self, data):
        for i in range(1, len(data)):
            index = i
            while self.less(data[index], data[index - 1]) and index > 0:
                self.exch(data, index, index - 1)
                index -= 1

    def less(self, x, y):
        return x < y

    def exch(self, data, i, min_index):
        data[i], data[min_index] = data[min_index], data[i]


if __name__ == "__main__":
    s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
    insertion = Insertion()
    insertion.sort(s)
    print(s)