插入排序的工作方式类似于排序一手扑克牌。

1. 整副牌分为2部分。

2. 左手是已经排序好的牌，右手是未排序的牌。

3. 初始时，左手有一张牌，右手是剩余的牌。

4. 右手从第二张牌开始和左手牌进行比较，因为左手牌是已经排好序的，所以从后往前进行比较。

5. 因为不需要额外的存储，所以在比较过程中，左手牌，要不断向后移动，给新的牌腾出位置。

6. 直到比较到开始位置，或找到新牌的位置，则停止向后移动。

7. 将新牌插入到找到的位置。

// Java代码void insertSort(int[] arr) {    // 从第二个位置开始比较    for (int i = 1; i < n; i++) {        // 先判断下当前相邻的两个数的大小，可以减少一次比较        if (a[i - 1] > a[i]) {                        int temp = a[i]; // 保存临时变量            int j = i; // 记录当前位置                        // 用当前位置的值，遍历和左侧已经排好序的数据进行比较            while (j > 0 && a[j - 1] > temp) { // 这个条件，和上面的if条件要一致                a[j] = a[j - 1]; // 数组向后移动位置，为新增加的数，腾出位置                j--; // 数组向前查找            }            a[j] = temp; // 将新的数插入到已经找到的位置        }    }}