2.1.3 插入排序 Insertion Sort

插入排序对于部分有序的数组十分高效，也很适合小规模数组。

部分有序：

• 数组中每个元素距离它的最终位置都不远
• 一个有序的大数组接一个小数组
• 数组中只有几个元素的位置不正确

Python

A = [70, 90, 31, 37, 10, 1, 48, 60, 33, 80]


def insert_sort(l):
    length = len(l)
    for i in range(1, length):
        x = l[i]
        for j in range(i, -1, -1):
            if x < l[j-1]:
                l[j] = l[j-1]
            else:
                break
        l[j] = x
    return l


print(insert_sort(A))

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]); i--)
                exch(a, j, j-1);
        }
    }
}