排序算法之希尔排序

插入排序存在的问题：

数组 arr = {2,3,4,5,6,1}， 这时需要插入的数是1，那么就要逐个将其他元素往后移，再把1放在首位。当需要插入的数是较小的数时，后移的次数明显增多，对效率很有影响。

希尔排序：

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

思路：

将数组arr分为 gap(arr.length / 2) 组，然后利用插入排序对同组的进行排序，这样可以将较小的数与同组比较之后快速调到前面来，减少移动次数。

将arr分为 gap / 2 组,然后继续利用插入排序将同组的调成有序。直到 gap = 1，利用插入排序将整个数组调成有序，则排序完成。

 代码：

 1     /**
 2      * 希尔排序
 3      * @param arr
 4      */
 5     public static void shellSort(int[] arr) {
 6         if (arr == null || arr.length == 0) {
 7             return;
 8         }
 9         //将arr分为gap组，组内元素的间隔为gap
10         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
11             //待插入有序数组的值
12             int insertValue;
13             //与insertValue做比较的值的下标
14             int index;
15             //无序数组的下标范围是 [gap, arr.length - 1]
16             for (int i = gap; i < arr.length; i++) {
17                 insertValue = arr[i];
18                 index = i - gap;
19                 //insertValue与有序数组依次比较
20                 while (index >= 0 && insertValue < arr[index]) {
21                     arr[index + gap] = arr[index];
22                     index -= gap;
23                 }
24                 arr[index + gap] = insertValue;
25             }
26         }
27     }