经典算法——直接插入排序

1. 算法的定义

任何被明确定义的计算过程都可以称作 算法 ，它将某个值或一组值作为输入，并产生某个值或一组值作为输出。所以 算法可以被称作将输入转为输出的一系列的计算步骤 。

说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码来表示，清晰的表达出思路和步骤，这样在真正执行的时候，就可以使用不同的语言来实现出相同的效果。

2. 直接插入排序

输入：😊

n个数的序列，通常存放在数组中可能是任意顺序。

输出：😃

输入序列的一个新排列(有顺序的)，满足从小到大(默认按照升序，通过简单的修改就可实现降序)

算法说明：😳

从原有的 无序 的序列中取出一个数（待排元素），插入到当前已经排好的 有序序列 当中，直到所有数全部取完，那么最后得到的新的序列也就是一个有序序列。最开始有序区里只有一个元素。

理解：😐
和打扑克牌一样，在抓起第一张牌的时候，直接放在手里面就可以。在抓后面牌的时候要和手里面的牌进行一个比较，然后才能决定后面的牌要放在哪里（后面抓起的牌就是待排元素）

过程 ：😠

将无序区中的元素一个一个插入到有序区当中的过程，最后输出的就是一个新的有序序列

1️⃣1. 第一个元素：放在第一个位置，直接排好
2️⃣2. 第二个元素：与第一个元素比较，如果更大，放在第二个位置，如果更小，放在第一个位置
3️⃣3. 第三个元素：顺序从后往前比较，如果更小，将已排好的元素向后串位，最后插入第三个元素
4️⃣4. 剩余其他元素：顺序从后向前比较，如果更小，将已排好元素向后串位，直到找到合适的位置插入
5️⃣5. 如果待排元素是已排好的元素中最大的，只需要比较一次，然后直接追加到已排好的序列后面

3. 代码实现

Java 代码实现⚠️⚠️⚠️

@Test
public void main() {
    // input data
    int[] a = {86, 34, 40, 7, 18, 38, 10, 57, 29, 47};
    // 数组下标从0开始，j初始为1，指向第二个元素
    for (int j = 1; j < a.length; j++) {
        // 使用key记录当前元素的值
        int key = a[j];
        // 初始化i，为j的前一个元素
        int i = j - 1;
        // while循环作用：在已经排好的有序数列中确定key的位置，并串出对应的位置
        while (i >= 0 && a[i] > key) {
            // 串位覆盖，不需要使用交换，值已经被记录在key中
            a[i + 1] = a[i];
            // 逐渐前移
            i = i - 1;
        }
        // 将待排元素放在对应的位置
        a[i + 1] = key;
    }
    // 查看排序结果
    for (int data : a) {
        System.out.print(data + "\t");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

4. 算法效率

4.1 时间复杂度

最坏的情况 👎

按照最坏的情况（每次插入都遍历一遍已经排好序的数组），外层循环n-1次，内层循环1+2+3+…+(n-2)=(n-2)(n-1)/2次，所以最坏情况是O(n²)

最好的情况 👍

最好的情况就是指能不被执行的步骤都没有被执行，来的数据刚刚好，并且每个数据都是这样。
对于直接插入排序来说，如果输入的元素已经是正向有序的，那么每次取出一个元素，在和已经排好的序列中的最后一个元素比较之后，就可以直接放到后面，循环都不用进，因为已经找到了它应该在的位置。
在这种情况下，内层的while循环可以只看成一个判断语句了，嗯，就是这样。所以代码执行的次数主要看外层for循环就好了，一共是n-1次，属于O(n)。

平均情况✌️
综合两种情况，插入排序的时间复杂度为 O(n²)。

4.2 空间复杂度

除计数器以外，算法执行过程中需要使用临时变量key来记录一下当前元素的值，除此之外的其他操作都可以在原数据结构（数组）上完成，所以空间复杂度为O(1)。