排序算法——插入排序

xiaop1ng   in ShenZhen

# 关于插入排序（insertion sorting）

大体含义是这样的，想我们在打扑克牌理牌时的思路一样，来一张扑克牌做一次插入操作。

20170609010214144.gif

下面我们给出普通版和优化版的插入排序

    public int [] insertionSort(int [] arr){
        for (int i = 1; i<arr.length;i++){
            for (int j = i; j>0 && arr[j] < arr[j-1];j--){
                int temp = arr[j];//循环比较两个相邻的值，满足排序条件做交换，不满足跳出当前这层循环
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
        return arr;
    }

    public int [] insertionSortPlus(int [] arr){
        for (int i = 1; i<arr.length;i++){
            int x = arr[i]; //记录当前抽的数
            int j;          //记录数的位置
            for (j = i; j>0 && arr[j-1] >x;j--){
                arr[j] = arr[j-1];//挪位置
            }
            arr[j] = x;     //最后处理当前抽的数的位置归宿 需要注意的是这里的 j 是上面 for 循环退出时的值
        }
        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

优化版的算法主要在于交换的次数上的优化，在数组本身的顺序较为良好的情况下，这种插入排序的优势可以体现出来，因为不用向冒泡或是选择排序那样必须走完内层循环，找到一个合适的时机可以提前跳出内层循环。

Gif Power By https://visualgo.net (opens new window)

关于插入排序（insertion sorting）