3.插入排序

介绍:

插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

1.算法步骤（n个数据升序）

把当前元素k左边当成一个有序数据（排好的升序）结构，然后依次和前面的一位比较,比k元素大的就往后移一位，如果前面一个比k元素小，k就放在这个小元素后面
1）第一轮：拿出第二个元素（第一个有序），和第一个元素比较，如果第一位比它大就换位置。
2）第二轮：拿出第三个元素（第一，二个元素是排好序的数据），把第三个元素和2号比较一下，如果2号大就把 2号往后移动一位，然后比较一号，如果2号小就不变，直接下一轮。
3）……
……
n-1)第n-1轮：拿出第n个元素（左边n-1个已排序），把第n个元素依次和n-1，n-2……比较，比n号元素大的往后移动一位，直到找到比n元素小的，就把n号元素放在这个小元素的后边一位

3.动图演示

3.代码实现

public class InsertSort implements IArraySort {
    @Override
    public int[] sort(int[] arr) throws Exception {
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }
}