简单排序--插入排序（JAVA）

简单排序分为冒泡排序，选择排序和插入排序。

插入排序主要思路：

（1）将一个数组分为有序列表和无序列表，左边是有序，右边是无序。(第一次排序开始时，有序列表为数组左边第一个元素，其余为无序列表)；

（2）每次排序只需要将无序列表的第一个元素插入到有序列表中，并保证插入后的有序列表保持有序。直到无序列表中没有元素。

假如有一个整数数组:  [ 15, 13, 7, 34, ........],

第一步：将整个数组分为有序列表而无序列表两部分，有序列表为[15],而无序列表为[13, 7, 34,....];

第二步：将无序列表的最左边的第一个元素（即13）与有序列表[15]中的各个元素比较由于13<15,则将元素13插入15的左边，最后结果是有序列表变为[13,15],而无序列表变为[7, 34, ...];此时第一次插入排序结束，数组变为[13,15,7,34,...];接下来开始第二次插入排序。

第三步：将无序列表[7, 34, ...]中的第一个元素7与有序列表[13,15]中的各元素比较。此时,会从有序列表的最右端开始比较.7会首先和15比较。由于7<15，则继续和有序列表中的下一个元素13比较,由于7<13，则继续和有序列表中的下一个元素比较，但元素13已经为有序列表的最后一个元素，因此将元素7插入到有序列表中元素13的左边。第二次插入排序结束。数组中有序列表为[7, 13, 15],无序列表为[34,....]。第二次插入排序后数组变成了[7,13,15,34,.......]。

第四步：继续将无序列表中的元素同有序列表中的元素比较并插入，直到无序列表中没有元素（就是一直比较到数组最后一个元素）。

主要代码如下：

    //  插入排序：将数组分为有序列表和无序列表，左边是有序，右边是无序，
    //  每次排序只需要将无序列表的第一个元素插入到有序列表中，并保证有序列表保持有序，
    //  复杂度为O（n²）因为比较次数与冒泡排序相同
    public void insertSort(Integer[] objects){
        // 默认数组的左边第一个元素有序，其余元素都是无序的,
        // 将无序列表中的左边第一个元素与有序列表中的最右边的第一个元素比较
        for(int i = 1;i<objects.length;i++){
            int temp = objects[i];//temp变量用于记录无序列表第一个元素（即最左边元素）的值
            int in = i;//额外声明一个变量in是为了in的值不会影响i的值
            //遍历有序列表，如果无序列表的第一个元素（即temp）小于有序列表中的元素
            while(in>0&&temp<objects[in-1]){
                objects[in]=objects[in-1];
                in--;
                System.out.println("while循环输出结果："+Arrays.toString(objects));
            }
            objects[in] = temp;
            System.out.println("--------------------------------------------------");
            System.out.println("第"+i+"次排序结果："+Arrays.toString(objects));
            System.out.println("--------------------------------------------------");
        }
    }

    public static void main(String[] args) {
        SelectSort selectSort = new SelectSort();
        //生成一个长度为15的随机数 数组
        Integer[] selectSortArray = new Integer[15];
        for(int i=0;i<selectSortArray.length;i++){
            int i1 = (int) (Math.random() * 1000);
            selectSortArray[i] = i1;
        }
        System.out.println("原数组"+Arrays.toString(selectSortArray));
        long startTime = System.currentTimeMillis();
        selectSort.insertSort(selectSortArray);
        long endTime = System.currentTimeMillis();
        //打印排序时间
        System.out.println(endTime-startTime);
    }

插入排序代码说明：

（1）变量i类似于一个指针，用于区分有序列表和无序列表。数组下标为i的元素左边（即下标从0到i-1）为有序列表，下标为i及其右边（即i到数组长度-1）的元素组成了无序列表。而i初始值为1说明第一个元素已经在有序列表中了，只需要从第二个元素开始即可；

（2）临时变量temp用于记录无序列表的第一个元素（就是需要插入到有序列表的元素）；

（3）变量in用于指向变量temp需要插入的位置；

（4）while循环：遍历有序列表，将无序列表中的第一个值（temp）与有序列表中的各个元素比较，如果变量temp比该元素小，则将该元素往后移动一个位置：objects[in]=objects[in-1]然后指针in往前移动一个位置，否侧该元素及in指针位置保持不变，直到while循环结束；

（5）将变量temp（即无序列表中的第一个元素）插入到指针in所在的位置。

拿刚才的数组画了个图：

如果还是不明白，可以将以上程序跑一遍，会打印数组在每一个循环中的值，如图：

        

最后，引用自书籍《数据结构与算法》中对复杂度的分析，其中的out就是本文中的变量i