希尔排序

算法思想：希尔排序是插入排序的改进版，现将序列按照一定步长分为子序列进行插入排序，最后步长为1，整体再插入排序。
代码实现：

public void shellSort(int[] a) {
        for(int increment=a.length/2;increment>0;increment/=2){
            for(int i = increment;i<a.length;i++){
                int temp = a[i];
                int j;
                for(j=i;j>=increment;j-=increment){
                     if(a[j-increment]>temp){
                         a[j] = a[j-increment];
                     }else{
                         break;
                     }    
                 } 
                 a[j]=temp;
            }
        }     
    }

另一种写法（for、while）

public void shellSort(int[] a) {
        for(int increment=a.length/2;increment>0;increment/=2){
            for(int i = increment;i<a.length;i++){
                int temp = a[i];
                int j = i - increment;
                while(j>=0 && a[j]>temp){
                    a[j+increment]=a[j];
                    j-=increment;
                }
                a[j+increment]=temp;
            }
        }     
    }

时间复杂度O(n^2)
稳定性：不稳定