本模块是公共类课程，适合绝大部分计算机岗位。由于 Java 受众最广且易读性强，本模块示例代码使用 Java 编写，其他语言也可参考学习。

插入排序原理

插入排序是一种简单的排序算法，主要思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的时间复杂度是 O(n^2)，空间复杂度是 O(1)。

插入排序实现

如，对数组 arr = [5, 3, 8, 6, 4] 进行升序插入排序。

默认第 0 个元素是有序的，

先让指针 i 指向数组第 1 个元素，表示未排序区域的第 0 个元素，每经过一轮插入，i++。

用temp保存i指向的元素。

每一轮让指针 j 指向 i - 1，然后依次向前比较，找到合适的位置插入当前元素。

排序过程如下：

1. 第一轮

   temp = arr[1] = 3

   5		8	6	4
   j	i

   arr[j] > temp，arr[j] 向后移动

   	5	8	6	4
   	i

   此时 j = -1，直接在数组头部插入 temp

   3	5	8	6	4

2. 第二轮

   temp = arr[2] = 8

   3	5		6	4
   	j	i

   arr[j] < temp，直接插入 temp

   3	5	8	6	4

3. 第三轮

   temp = arr[3] = 6

   3	5	8		4
   		j	i

   arr[j] > temp，arr[j] 向后移动

   3	5		8	4
   	j		i

   arr[j] < temp，直接插入 temp

   3	5	6	8	4

4. 第四轮

   temp = arr[4] = 4

   3	5	6	8
   			j	i

   arr[j] > temp，arr[j] 向后移动

   3	5	6		8
   		j		i

   arr[j] > temp，arr[j] 向后移动

   3	5		6	8
   	j			i

   arr[j] > temp，arr[j] 向后移动

   3		5	6	8
   j				i

   arr[j] < temp，直接插入 temp

   3	4	5	6	8

   i 已经到达数组末尾，排序结束。

插入排序代码实现

public void insertionSort(int[] nums) {
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        int key = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
}