基本思想

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

image

算法实现

package cn.caojiantao.tutorials.sort;

/**
 * @author caojiantao
 */
public class Insert implements ISort {

    @Override
    public void sort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int key = data[i], j = i - 1;
            for (; j >= 0; j--) {
                if (key < data[j]) data[j + 1] = data[j];
                else break;
            }
            data[j + 1] = key;
        }
    }
}

复杂度

• 时间复杂度 O(n²)
• 空间复杂度 O(1)