什么是希尔排序

排序原理：

将一组数组分成若干份，每份里的数比较并排序，最后再将所有的总体排序。

例子：

给这个数组排序{1，9，6，4，8，5，3，2}

一般都是第一次分成两两一组也就是让同一组的数字间隔是数组数的1/2，间隔是4，一共分成四组

第一次分类结果如下：

{
1，9，6，4，8，5，3，2}

相同颜色的为一组，下一步将同一组的数字进行比较，

第一次排序结果如下：

{
1，5，3，2，8，9，6，4}

第二次分类是在第一次的基础上更加细化，间隔再小1/2，间隔是2，一共分成两组

第二次分类结果如下：

{
1，5，3，2，8，9，6，4}

第二次排序结果如下：

{
1，5，3，2，6，9，8，4}

第三次分类是在第二次的基础上更加细化，间隔再小1/2。间隔是1，也就是没有间隔

第三次分类结果如下：

{
1，5，3，2，6，9，8，4}

第三次排序结果如下：

{
1，2，3，4，5，6，8，9}

代码主体：

 //用希尔法排序数组
    public static void main(String[] args) {
       //定义要排序的数组
        int[] ary = new int[]{1, 8, 9, 5, 4, 2, 6, 7, 3, 10};
        System.out.println(Arrays.toString(ary));
       //第一个for定义希尔排序的间隔，只要内部循环结束就给间隔/2
        for (int i = ary.length / 2; i > 0; i = i / 2) {
            /**
             * 第二个for用来控制第三个for的循环
             * age++确保第三个for的j每次往前进1
             */
            for (int age = i; age < ary.length; age++) {
                /**
                 * 最后一个for功能最多
                 * j=age-i确保了比对的数组顺序从0开始挨个往后
                 * j>=0要和j=j-i合起来看
                 * 他俩合起来的功能是当一个数在它的希尔组中并不排第一个时
                 * 它和后面的比较完大小时，还要将该位置的数和前一个比大小
                 * 这两句还有上一个for的age++合起来就有这样的效果
                 * 所以当大循环进行第一次时不会有效果，但当进行第二次时就有效果了
                 */
                for (int j = age - i; j >= 0; j = j - i) {
                    //进行具体的执行
                    int tem = ary[j];
                    //判断同一希尔组里相邻的两个数的大小
                    //如果前大于后就交换位置
                    //保证前小后大
                    if (ary[j] > ary[j + i]) {
                        ary[j] = ary[j + i];
                        ary[j + i] = tem;
                    }
                }
            }
        }
        //输出
        System.out.println(Arrays.toString(ary));
    }
}

输出结果：

[1, 8, 9, 5, 4, 2, 6, 7, 3, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Process finished with exit code 0

原文链接: https://blog.csdn.net/daibadetianshi/article/details/137054265