1.1希尔排序（插入排序的改良）

0.算法解决的问题

为了减少插入排序（朴素的排序算法）所耗时间，我们采取一种基于其原理的，但是不同思想的算法.

1.输入与输出

• 输入：乱序的数组
• 输出：排好序的该数组

2.算法思想

把数组中间隔为h的元素取出来看作一个单独的数组进行排序。假设h＝3，
那么可以把数组分为

a[0],a[3],a[6]……

a[1],a[4],a[7]……

a[2],a[5],a[8]……

所谓的h有序数组

如上图所示，先将拆分过后的小数组进行排序，缩小h后再次排序。直到h＝1，排序完成。

3.伪代码及注释

三个循环分别代表：h值不断缩小，一个h值中排序的组不断变化，插入排序。

4.java代码实现

public static int[] shellSort(int[] a)
    {
    int temp=0;
    int n = a.length;
    int h,j;
     for (h = n / 2; h > 0; h /= 2)  
    for (j = h; j < n; j++)//从数组第h个元素开始  
        if (a[j] < a[j - h])//每个元素与自己组内的数据进行直接插入排序  
        {  
            temp = a[j];  
            int k = j - h;  
            while (k >= 0 && a[k] > temp)  
            {  
                a[k + h] = a[k];  
                k -= h;  
            }  
            a[k + h] = temp;  
        }                  
    return a;
}

5.复杂度

对于近似有序的数组来说，插入算法的速度是很快的。
相比于传统的插入算法，希尔算法每次将元素移动的距离增大了h，这解决了移动距离远的情况下移动距离次数多这一问题。

6.优缺点及适用范围

适用于大型的，静态的数据库。