栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法基础|再次实现希尔排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法基础|再次实现希尔排序

希尔排序

希尔排序是高级排序的一种,希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。

在代码上最大的不同在于其有个步长变量,该变量随着大循环不断减少至1,这个步长变量控制每次插入排序的分组。

伪代码如下:

while(true){
    定义步长;
    
    while(true){
        根据步长进行分组,然后对每组进行插入排序
    }
    
    减少步长;
    if(步长==1){
        break;
    }
}

老韩牛逼,老韩的实现方法教学如下:
首先实现第一步,在起始步长时,对各组进行排序

    public static void sort2(int[] arr) {
        //int[] arr = {-7, 6, 5, 4, 3, 2, 1};
        //首先实现第一步,在起始步长时,对各组进行排序
        //起始步长为3
        int length = arr.length;

            //分组排序
            //直接把步长写死,方便理解!
            for (int i = 0; i < length; i++) {
                //边界判断
                if (i + 3 >= length) {
                    break;
                }
                for (int j = i; j < length; j = j + 3) {
                    if (j + 3 >= length) {
                        break;
                    }
                    //如果指针处数值小于临近左边的数
                    if (arr[j] > arr[j + 3]) {
                        int temp = arr[j + 3];
                        arr[j + 3] = arr[j];
                        arr[j] = temp;
                    }
                }

            }
    }

对上面那个一步的算法进行扩展,扩展到步长自动减少:

public static void sort2(int[] arr) {
    //确定起始步长
    int length = arr.length;
    int h = length / 2;

    while (h >= 1){
        //这是我自己写的,比较符合直观的方法,可以优化边界
        //分组排序
        for (int i = 0; i < length; i++) {
            if (i + h >= length) {
                break;
            }
            for (int j = i; j < length; j = j + h) {
                if (j + h >= length) {
                    break;
                }
                //如果指针处数值小于临近左边的数
                if (arr[j] > arr[j + h]) {
                    int temp = arr[j + h];
                    arr[j + h] = arr[j];
                    arr[j] = temp;
                }
            }

        }
        //减少步长
        h = h / 2;
    }
}

上面算法还是继续修改一下(边界条件判断优化),最后得到:

    public static void sort(int[] arr) {
        //首先确定一个增长量h
        //每次循环结束后h/2,只要h>1,就不会报错
        int h = 1;
        while (h < arr.length * 0.8) {
            h = h * 2 + 1;
        }

        while (h >= 1) {
            //这个属于比较机灵的做法,就是i从h开始,这样就可以少一次边界判断。
            //找到待插入数(记住,希尔排序是插入排序的升级版,本质还是插入排序)
            //循环一次,就是对一个数组进行排序
            for (int i = h; i < arr.length; i++) {
                //循环一次,就是进行一次比较
                for (int j = i; j >= h; j = j - h) {
                    if (arr[j] < arr[j - h]) {//arr[j]是后一个数,arr[j-h]是前一个数,h是步长
                        int temp = arr[j - h];
                        arr[j - h] = arr[j];
                        arr[j] = temp;
                    } else {
                        break;
                    }
                }
            }
            h = h / 2;
        }
    }


常言道软件开发的思想是快速实现,然后不断迭代,我想,算法实现也是如此。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970037.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号