直接插入排序（插入排序）

一、算法实现

• 基本实现

/**
 * 直接插入排序（插入排序）
 */
public static int[] sortInsert(int[] arr) {
    int i, j, temp;
    for (i = 1; i < arr.length; i++) {
        temp = arr[i];
        for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = temp;
    }
    return arr;
}

二、运行示例

{20, 15, 10, 12}
[【15】, 20], 10, 12 //--> 选择[1]位置的数与前面的数进行重新排序
[【10】, 15, 20], 12 //--> 选择[2]位置的数与前面的数进行重新排序
[10, 【12】, 15, 20] //--> 选择[3]位置的数与前面的数进行重新排序

三、性能分析

• 时间复杂度

1.当原始序列“正序”时，直接插入排序效果最好，所以直接插入排序最好情况下时间复杂度为O(n)
2.当原始序列“逆序”时，直接插入排序效果最差，所以直接插入排序最坏情况下时间复杂度为O(n^2)
3.直接插入排序平均时间复杂度为O(n^2)

• 空间复杂度

空间复杂度为O(1)

• 稳定性

是稳定的排序算法

原文：经典排序算法（3）——直接插入排序算法详解