算法回顾之五：希尔排序(缩小增量排序)

算法回顾系列第五篇：希尔排序

---------------------------------------

希尔排序(缩小增量排序)

 

基本原理：

该方法实质上是一种分组插入排序方法，属于直接插入排序的改进算法。

比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。

 

算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d。

对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。

当增量减到1时，整个要排序的数被分成一组，排序完成。

(一般初次取序列一半为增量，然后每次减半，直到增量为1。)

 

程序实现：

public void sort(int[] data) {
    	//初次取序列长度一半为增量(相隔距离),以后每次减半,直到增量为1.
        for(int i=data.length/2;i>2;i/=2){//i为增量,若大于2,则每次递减一半.
        	//每次增量缩小后都需要从头进行一次排序.
            for(int j=0;j<i;j++){
                insertSort(data,j,i);//起始为0,增量不为1的插入排序.
                System.out.println("after insert sort:"+Arrays.toString(data));
            }
            System.out.println("sort:"+Arrays.toString(data));
        }
        insertSort(data,0,1);//起始为0,增量是1的直接插入排序.
        System.out.println("after final sort:"+Arrays.toString(data));
    }
    
    /**
     * 与直接插入排序实现类似,只不过增量不一定为1(不是相邻元素交换位置).
     * @param data 待排序数组
     * @param start 起始位置
     * @param inc 增量
     */
    private void insertSort(int[] data, int start, int inc){
        int temp;
        for(int i=start+inc;i<data.length;i+=inc){
            for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
                temp = data[j];
				data[j] = data[j-inc];
				data[j-inc] = temp;
				//System.out.println("after swap:"+Arrays.toString(data));
            }
        }
    }
    
    public static void main(String[] args){
    	int[] data = new int[]{12,11,10,9,8,7,6,5,4,3,2,1};
    	new ShellSort().sort(data);
    	System.out.println(Arrays.toString(data));
    }

上面程序中： 

一共12个元素，增量分别为6,3,1.

第一次以6为增量分组，每组元素(相差距离为6)进行直接插入排序。

第二次以3为增量分组，每组元素(相差距离为3)进行直接插入排序。

最后以1为增量分组(即全部元素)，进行一次直接插入排序。

 

性能分析：

平均时间复杂度 O(nlogn)，最差时间复杂度O(n^2)。

 

空间复杂度：1。

稳定性：不稳定。