[数据结构与算法]什么是插入排序？

插入排序

简介

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

简单来说，就是将要排序的元素，分为两部分，一部分为有序表，一部分为无序表，每次从无序表中取出一个元素插入到有序表中。
刚开始第一个元素我们认为他是有序的，把后面的元素逐个插入到前面的有序队列中。

比如说：
序列[5,2,4,6,1,3]

有序：5
无序：2，4，6，1，3

第一次将2插入有序序列中
第一次插入后

有序：2，5
无序，4，6，1，3

第二次插入4
第二次插入后

有序：2，4，5
无序：6，1，3

第三次次插入6
第三次插入后

有序：2，4，5 ，6
无序：1，3

第四次插入1
第四次插入后

有序：1，2，4，5 ，6
无序：3

第五次插入3
第五次插入后

有序：1，2，3，4，5 ，6
无序：NULL

插入排序是稳定的；

代码：

//定义两个变量用来存储插入的数值，和将要插入的下标
        int insertValue;
        int insertIndex;
        //默认第一个数是有序的，从第二个数开始判断，直至最后一个数。
        for (int i = 1; i < arr.length; i++) {
            insertValue = arr[i];//待插入的值
            insertIndex = i - 1;//待插入的位置，第一次是要插入的前一个位置，然后往前移动
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {//如果待插入位置的数小于待插入的数就将此数后移；
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //当while循环结束，说明已经找到这个数，此时待插入处的索引，不符合，所以待插入的位置应为insertIndex+1;
            //比如当索引为-1时，退出，则值应插入0处
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertValue;
            }
        }