插入排序

基本思想:

每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

Java实现

public static void insertSort(int[] numbers) {
    int size = numbers.length;
    int temp = 0;
    int j = 0;
    for (int i = 1; i < size; i++) {
        temp = numbers[i]; 
        // 假如temp比前面的值小，则将前面的值后移
        for (j = i; j > 0 && temp < numbers[j-1]; j--) {
            numbers[j] = numbers[j-1];
        }
        numbers[j] = temp;
    }
}

时间复杂度O(n*n)

性能上优于冒泡排序和选择排序