排序算法-希尔排序

算法思想

希尔排序又叫做缩小增量排序，本质还是插入排序，只不过是将待排序列按照某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。如果增量为1，就是直接插入排序。

例如,先以增量为5来分割序列，即下表为0、5、15、…的关键字分为一组，将下标为1，6，11，16，…的关键字分为另一组等，然后分别对这些组进行直接插入排序，就组成了一趟希尔排序。将上边排好序的整个序列，再以增量2分割，即将下标为0、2、4、6、8、…的关键字分为一组，将1、3、5、7、9…的关键字分为另一组等，然后分别对这些组进行直接插入排序，即完成又一次希尔排序。最后以增量1分割整个序列，即对整个序列进行一趟直接插入排序，从而完成整个希尔排序。

注意到增量5、2、1是逐渐缩小的，所以称为缩小增量排序。

直接插入排序适合于序列基本有序的情况，希尔排序的每趟排序都会使整个序列变得更加有序，等整个序列基本有序了，再做一次直接插入排序，这样会使排序效率更高。

缩小增量的选取

1. 增量一般选择为$\lfloor n/2\rfloor$ 、$\lfloor n/4\rfloor$、$\lfloor n/2^k\rfloor$、… 2 、1。
   即每次将增量除以2并向下取整，其中n为序列长度，此时时间复杂度为$O(n^2)$
   希尔排序的空间复杂度与直接插入排序一样，为$O(1)$.
2. 增量选择为：$2^k+1$、…、$9、5、3、1$时，时间复杂度为$O(n^{1.5})$.
   其中，k为大于等于1的整数，$2^k+1$小于待排序列长度，增量序列末尾的1是额外添加的。

代码

public class Shellsort {
    public static void main(String[] args) {
        int[] nums = {3,8,4,5,6,8,9,0};
        shellsort(nums,nums.length);
        for(int num:nums){
            System.out.print(num);
        }
    }
    public static void shellsort(int[] nums, int n){
        int i,j;
        for(int d = n/2;d>=1;d=d/2){  //步长变化
            for(i=d;i<n;++i){         //有增量的遍历数组,接下来全是简单插入排序只不过加入了增量而已。
                int temp = nums[i];   
                if(nums[i]<nums[i-d]){       
                    for(j = i-d;j>=0 && temp<nums[j];j=j-d){
                        nums[j+d] = nums[j];
                    }
                    nums[j+d] = temp;
                }
            }
        }
    }

}