java算法：插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。

插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，如下图所示：

image.png

排序原理：
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。刚开始这个小序列只包含第一个元素，事件复杂度O(n2)。比较是从这个小序列的末尾开始的。想要插入的元素和小序列的最大者开始比起，如果比它大则直接插在其后面，否则一直往前找它该插入的位置。如果遇见了一个和插入元素相等的，则把插入元素放在这个相等元素的后面。所以相等元素间的顺序没有改变，是稳定的。

image.png

写法一：

/**
     * 插入排序
     * 原始数据：4,3,2,10,12,1,5,6
     * 第一轮 ：[3,4],2,10,12,1,5,6
     * 第二轮 ：[2,3,4],10,12,1,5,6
     * 第三轮 ：[2,3,4,10],12,1,5,6
     * 第四轮 ：[2,3,4,10,12],1,5,6
     * 第五轮 ：[1,2,3,4,10,12],5,6
     * 第六轮 ：[1,2,3,4,5,10,12],6
     * 最后一轮 ：[1,2,3,4,5,6,10,12]
     */
    public void insertSort01() {
        int[] arr = {4,3,2,10,12,1,5,6};
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                //比较索引j处的值和索引j-1处的值，如果索引j-1处的值比索引j处的值大，则交换数据，如果不大，那么就找到合适的位置了
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
        Log.i(TAG, "插入排序结果："+ Arrays.toString(arr));
    }

输出结果：

插入排序结果：[1, 2, 3, 4, 5, 6, 10, 12]

写法二：

/**
     * 插入排序
     * 原始数据：4,3,2,10,12,1,5,6
     * 第一轮 ：[3,4],2,10,12,1,5,6
     * 第二轮 ：[2,3,4],10,12,1,5,6
     * 第三轮 ：[2,3,4,10],12,1,5,6
     * 第四轮 ：[2,3,4,10,12],1,5,6-->过程分解：[2,3,4,10,1,12],5,6->[2,3,4,1,10,12],5,6->[2,3,1,4,10,12],5,6->[2,1,3,4,10,12],5,6->[1,2,3,4,10,12],5,6最终到第五轮
     * 第五轮 ：[1,2,3,4,10,12],5,6
     * 第六轮 ：[1,2,3,4,5,10,12],6
     * 最后一轮 ：[1,2,3,4,5,6,10,12]
     */
public void insertSort02() {
        int[] arr =  {4,3,2,10,12,1,5,6};
        for (int i = 1; i < arr.length; i++) {
            int insertValue = arr[i];//要插入排序的元素
            int j = i - 1;
            //从右向左找insertValue的插入位置
            while (j >= 0 && insertValue < arr[j]) {
                arr[j+1] = arr[j];//将大于insertValue的元素右移
                j --;//新的小组里j逐渐递减
            }
            if (j + 1 != i) {
                arr[j+1] = insertValue;//在j+1处插入insertValue
            }
        }

        Log.i(TAG, "插入排序结果："+ Arrays.toString(arr));
    }

输出结果：

插入排序结果：[1, 2, 3, 4, 5, 6, 10, 12]

插入排序的时间复杂度分析
插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析插入排序的时间复杂度，主要分析一下内层循环体的执行次数即可。
最坏情况，也就是待排序的数组元素为{12,10,6,5,4,3,2,1}，那么：
比较的次数为：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
交换的次数为：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
总执行次数为：(N2/2-N/2)+(N2/2-N/2)=N^2-N;

按照大O推导法则，保留函数中的最高阶项那么最终插入排序的时间复杂度为O(N^2).

参考：
https://www.cnblogs.com/momo-88/p/13423667.html
https://www.cnblogs.com/yuanchangliang/p/16373111.html