算法描述

直接插入排序算法描述如下: 设线性序列是{a0,a1,…ai-1,ai,…,an-1}。

  1. 第 i (1 <= i < n)趟，设前 i 个元素构成的{a0,a1,…,ai-1}子序列是排序的，将元素 ai 插入 {a0,a1,…,ai-1} 的适当位置，使插入后的子序仍然是排序的，ai 的插入位置由关键字比较大小确定的。
  2. 重复执行 1，n个元素共需进行 n - 1 趟排序，每趟将一个元素 ai 插入前面的子序列。区别两个关键字相同元素，其中 {} 表示已排序子列。

时间复杂度 平均情况：O(n^2) 最坏情况：O(n^2),该情况出现在原序列为逆序情况
最好情况：O(n)，出现在已经为升序排列的情况，每次之比较一次即可，共 n - 1 次循环，故为 n - 1
稳定性：稳定

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 /**
 * 插入排序
 * @param arr
 * @param orderBy [asc 升序，desc降序]
 */
public static void sort(int[] arr, String orderBy) {
    for (int i = 1; i < arr.length; i++) { // n - 1 趟，依次向前插入 n - 1 个数
        int x = arr[i], j; // 每趟将arr[i]插入到前面的子序列中
        // asc  如果 x 小于前一个元素 执行循环中的代码否则结束循环
        // desc 如果 x 大于前一个元素 执行循环中的代码否则结束循环
        for (j = i - 1; j >= 0 && (orderBy.equals("asc") ? x < arr[j] : x > arr[j]); j--) {
            arr[j + 1] = arr[j]; // 将前面较大/较小的元素向后移动
        }
        arr[j + 1] = x; // x 值到达插入位置
    }
}