插入排序算法
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
插入算法把要排序的数组分成两部分：
第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），
而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
希尔排序
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
算法复杂度：下界是O(n/*log2n),与增量序列的选取有关 不稳定
算法思想：
- 确定增量（默认以数组长度的一半为增量）
- 循环增量，通过增量将数组分成若干段，进行比较
- 俩段中的相对位置进行比较，替换大小
- 缩小增量，反复循环
/**
* 希尔排序
* 2017年8月23日 下午9:47:36
*
*/
public class HeerSort> {
/**
* 希尔排序算法
* @param array
*/
public void heerSort(T[] array) {
// 取分组数，每隔多少个一比较
// 比较粒度
int num = array.length / 2;
// 一直循环
while (true) {
// 根据比较粒度，进行循环分组比较
for (int i = 0; i < num; i++) {
// 通过循环让i下标元素与后面对应位置的元素进行比较
// j+num<array.length:该意义为对应的位置不超过数组长度
// j+=num:更换要比较的位置下标
for (int j = i; j + num < array.length; j += num) {
// 比较当前位置和下一个位置的大小，
if (array[j].compareTo(array[j + num]) == 1) {
// 交换数据
T temp = array[j];
array[j] = array[j + num];
array[j + num] = temp;
}
}
}
// 如果比较粒度为1，则跳出循环
if (num == 1) {
break;
}
// 递减比较粒度，从数组长度一半到1，依次进行粒度比较
--num;
}
}
public static void main(String[] args) {
Integer[] array = { -1, 5, 98, 7, 45, 98, -4, 9888, 45, 1, 5, 7, 5, 6,
8, 85, 75, 45, };
HeerSort sort = new HeerSort();
sort.heerSort(array);
for (Integer integer : array) {
System.out.println(integer);
}
}
}
