希尔排序

在插入排序中，我们假设在即将进行排序的元素的左侧所有的元素已经是有序的，所以我们会将该元素与它左侧的元素逐个比较，如果左侧的元素大于该元素，则左侧的元素右移。然后，该元素继续与左侧的下一个元素比较。现在有一个问题：极端情况下，刚开始很小的元素放到了最右侧，那么它左侧所有的元素都要向右移动复制一次，这样效率是很低的，那么如何解决呢？可以考虑希尔排序。希尔排序是基于插入排序的，它通过加大插入排序中元素的间隔，从而使得元素能够大跨度的移动，这样能减少移动次数。经过一趟排序后，然后减小间隔再排序，直至最后一次排序的间隔为1，这最后一次的排序其实就是插入排序。这里，涉及到一个间隔h，一般情况下，我们使用h = 3*h+1。注意：颜色相同的元素都进行了排序。

情景：对数组 int[] arr = {7，10，1，9，2，5，8，6，4 ，3}中的数据从小到大排序。

第一趟排序前：7 10 1 9 2 5 8 6 4 3 第一趟排序后：2 3 1 6 4 5 8 9 7 10 （h = 4）

第二趟排序前：2 3 1 6 4 5 8 9 7 10 第二趟排序后：1 2 3 4 5 6 7 8 9 10 （h = 1）

代码：

/**
 * 希尔排序
 * @author D N
 *
 */
public class ShellSort {
    private long[] a; 
    private int nElems;
    
    public ShellSort(int max){
        a = new long[max];
        nElems = 0;
    }    
    
    public void insert(long value){
        a[nElems] = value;
        nElems++;
    }
    
    public void display(){
        for(int j=0;j<nElems;j++){
            System.out.print(a[j]+"   ");
        }
        System.out.println("");
    }
    
    
        //希尔排序算法 
        public void shellSort(){
            int inner,outer;
            long temp; // 临时变量
            
            int h = 1; //数据项之间的间隔，排序时按此间隔排序
            while(h <= nElems/3 ){
                h = h*3+1;
            }
            
            while(h > 0){ //不断减少h，直至h = 1，此时排序成为了插入排序
                for(outer = h;outer < nElems;outer++){
                    temp = a[outer];
                    inner = outer;
                    while(inner > h-1 && a[inner-h] >= temp){
                        a[inner] = a[inner-h];
                        inner -= h;
                    }
                    a[inner] = temp;
                }
                h = (h-1)/3;
                display();
            }
            
        }
}

运行测试代码：

public class SortTest {
    public static void main(String[] args) {
        int maxSize = 10;
        ShellSort arr = new ShellSort(maxSize);
        arr.insert(7);
        arr.insert(10);
        arr.insert(1);
        arr.insert(9);
        arr.insert(2);
        arr.insert(5);
        arr.insert(8);
        arr.insert(6);
        arr.insert(4);
        arr.insert(3);
        arr.display();
        System.out.println();
        arr.shellSort();
        System.out.println();
        arr.display();
    }
}

运行结果：

7   10   1   9   2   5   8   6   4   3   

2   3   1   6   4   5   8   9   7   10   
1   2   3   4   5   6   7   8   9   10   

1   2   3   4   5   6   7   8   9   10

效率分析：

希尔排序效率比插入排序要高，在有几千个元素需要排序时，它的效率更容易显现出来。原因就是：当h大的时候，每一趟排序需要移动的元素个数很少，但是移动的距离很长，这很有效率。当h减少时，每一趟排序需要移动的次数增多，但是此时数组已经接近排序后最终的位置，当h=1时，希尔排序也就成为了插入排序。