《Algorithms》Comparable 实现希尔排序

标签: 希尔排序  Java  算法  排序

原文链接:https://blog.csdn.net/Lee199598/article/details/88087053

希尔排序

希尔排序其实是改进版的插入排序,我们先回忆一下插入排序,插入排序每次将已排序序列的后一位元素插入到前面已排序的序列中,重点是这个插入的过程,其实和冒泡排序的思想是一样的,它是一位一位的移动,这样子效率很明显是低下的。而插入排序对于部分有序的数组进行排序又是高效的,希尔排序就是利用这两点对插入排序进行了改进。

希尔排序又名缩小增量排序。这里的增量是第一个需要理解的重点,希尔排序是先将待排序序列分为h组,最少自然是全部作为一组,即h>=1。每组中元素的间隔为h,这里的h就是增量。而增量的选取是一个数学难题,我们暂且选择书上的增量,1~N/3。举个例子:

有如下数组:
在这里插入图片描述

上图两个数组,下面的按颜色分组,组内元素之间的距离就是增量h,共h组。

第一组:8 -6 7 9

第二组:-3 0 2

第三组:4 6 1

对每一组进行插入排序,结果为下图
在这里插入图片描述
第一组:-6 7 8 9

第二组:-3 0 2

第三组:1 4 6

每一组已完成排序,下一步就是减小增量,h = h/3 = 1;分组后数组如下图:
在这里插入图片描述
然后对上面的数组进行插入排序:
在这里插入图片描述
希尔排序对比直接插入排序更高效的原因就是它利用了插入排序对部分有序数组排序的高效并解决了插入排序插入时“冒泡插入”的低效。

代码如下:

public class ShellSort {
    /**
     * 判断元素m是否小于n
     * */
    private static boolean less(Comparable m, Comparable n){
        return m.compareTo(n) < 0;
    }
    /**
     * 交换元素顺序
     * */
    public static void exchange(Comparable [] a, int m, int n){
        Comparable temp = a[m];
        a[m] = a[n];
        a[n] = temp;
    }
    /**
     * 判断是否成功排序
     * */
    public static boolean isSorted(Comparable [] a){
        for (int i = 1 ; i < a.length ; i++ ) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }
    /**
     * 展示数组元素
     * */
    public static void show(Comparable [] a){
        for (int i = 0 ; i < a.length ; i++ ){
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    /**
     * 希尔排序算法(升序排列)
     * */
    public static void sort(Comparable [] a){
        int len = a.length;
        int h = 1;
        while(h < len/3) { // 确定初始增量大小
            h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093
        }

        while (h >= 1) { // 最少将数组分为一组
            for (int i = h ; i < len ; i++){
                for (int j = i ; j>=h && (less(a[j], a[j-h])) ; j-=h){
                    exchange(a, j, j-h);
                }
            }
            h = h/3;
        }
    }
    
   
}

测试用例:

public static void main(String[] args) {
    Comparable [] a = new Comparable[20];
    for (int i = 0 ; i < a.length ; i++){
        a[i] = new Random().nextInt(50);
    }
    System.out.print("排序前:");
    show(a);
    sort(a);
    System.out.print("排序后:");
    show(a);
    System.out.println(isSorted(a));
}

运行效果:

排序前:6 1 26 48 21 47 26 47 18 1 23 5 1 32 44 27 8 19 49 44 
排序后:1 1 1 5 6 8 18 19 21 23 26 26 27 32 44 44 47 47 48 49 
true
原文链接:加载失败,请重新获取