java实现排序算法之插入排序（直接插入排序、折半插入、shell排序）
插入排序主要包括直接插入排序、shell排序和折半插入等几种排序。这篇文章主要说明直接插入排序、shell排序和折半插入三种排序的java实现。
一、直接插入排序
直接插入排序(straight insertion sort)的作法是：
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。
值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。
二、折半插入排序
折半插入排序的基本思想是:设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中，V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半查找法寻找V[i]的插入位置。
三、shell排序
希尔排序基本思想
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
算法步骤
Step1 将n个元素个数列分为5个小组，在每个小组内按直接插入法排序；
step2 在第i步，分组个数取 di+1 =（di +1）/2 {9，5，3，2，1}；相临两组之间的对应元素进行比较，如果ai>aj，则交换它们的位置；
Step3 当dK = 1的循环过程完成后，排序过程结束。
Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插人排序有较大的改进。
稳定性
希尔排序是不稳定的。
