希尔排序

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
需求
排序前：{9,1,2,5,7,4,8,6,3,5}
排序后：{1,2,3,4,5,5,6,7,8,9}

排序原理

1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
2.对分好组的每一组数据完成插入排序；
3.减小增长量，最小减为1，重复第二步操作。


增长量h的确定：增长量h的值每一固定的规则，我们这里采用以下规则：

int h = 1;
while (h < a.length){
  h = 2*h+1;
}

 //减小h的值
h=h/2;

希尔排序的API设计

希尔排序的代码实现

import java.util.Arrays;

/**
 * @author: ChengLong
 * @datetime: 2021/5/23 9:50
 */
public class Demo04Shell {


    public static void main(String[] args) {
        Integer[] arr = {9,1,2,5,7,4,8,6,3,5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /*
     1.对数组内的元素进行排序
    * */
    public static void sort(Comparable[] a) {
        // 1、根据数组a的长度确定增长量h的初始值
        int h = 1;
        while (h < a.length){
            h = 2*h+1;
        }
        // 2、希尔排序
        while (h>=1){
            //排序
            //2.1找到待插入的元素
            for (int i = h;i<a.length;i++){
                //2.2把待插入的元素插入到有序元素中
                for (int j = i;j>=h;j-=h){
                    //待插入的元素是a[j],比较a[j]和a[j-h]
                    if (greater(a[j-h],a[j])){
                        //交换元素
                        exch(a,j-h,j);
                    }else {
                        //待插入元素已经找到了合适的位置，结束循环
                        break;
                    }
                }
            }
            //减小h的值
            h=h/2;
        }
    }
    /*2.:判断v是否大于w
     * */
    private static boolean greater(Comparable v,Comparable w){

        return v.compareTo(w) > 0;
    }

    /*
     3.交换a数组中，索引i和索引j处的值
    * */
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

希尔排序的时间复杂度分析

在希尔排序中，增长量h并没有固定的规则，有很多论文研究了各种不同的递增序列，但都无法证明某个序列是最
好的，对于希尔排序的时间复杂度分析，已经超出了我们课程设计的范畴，所以在这里就不做分析了。

希尔排序

原文：https://www.cnblogs.com/chenglong0201/p/14791535.html