1、基本思想

　　在要排序的一组数中，按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。

2、代码示例

package  sort;/** * 希尔排序（最小增量排序）  * */public class ShellSort {        public void TestSort() {        int a[]={1,54,6,3,78,34,12,45,56,100};         sort(a);        sort2(a);    }        public void sort(int arr[]){         //数组长度        int len=arr.length;         //临时变量        int temp=0;         //增量d（n/2,n为要排序数的个数）        int d=len;        while(true){            d=d/2;            //直接插入排序            for(int k=0;k
     
      =0&&temp
      
        0; gap /= 2) {
   //步长            for (i = 0; i < gap; i++)        //直接插入排序            {                for (j = i + gap; j < len; j += gap)                     if (arr[j] < arr[j - gap])                    {                        int temp = arr[j];                        int k = j - gap;                        while (k >= 0 && arr[k] > temp)                        {                            arr[k + gap] = arr[k];                            k -= gap;                        }                        arr[k + gap] = temp;                    }            }        }        for (i = 0; i < arr.length; i++){            System.out.print(arr[i] + " ");        }    }}
      
     

3、效率分析