插入排序之shell排序教程

插入排序分为两种：直接插入排序、希尔排序

一、shell排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。它是基于插入排序的改造而来的（第一个突破O(n^2)的排序）。

算法描述：相对于直接插入排序的一步一步比较、移动、排序，shell排序将对要排序的数据分为几组数组（gap决定），然后分组进行直接插入排序，在缩减gap，重复在组内进行直接插入排序，直到gap=1。

演示：

除始数据：

初始gap=arr.length/2 = 3,所以数据被分为三组【6,3】、【5,2】、【4,1】，然后对这三组数据进行直接插入排序，

然后gap=3/2=1，所以为一整个数组【3,2,1,6,5,4】,整个数组的有序性大大增加。

代码：

<pre class="has">

private static void shellSort(int[] arr) {

    //控制增量的大小
    for (int gap = arr.length/2; gap > 0; gap/=2) {
        //遍历每个分组
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            int temp = arr[i];
            //对每个分组进行直接插入排序
            while(j>= gap && temp < arr[j-gap]) {
                arr[j] = arr[j-gap];
                j-=gap;
            }
            arr[j] = temp;
        }
    }
}