请选择 进入手机版 | 继续访问电脑版

排序算法第一谈:希尔排序

[复制链接]
小浣熊 发表于 2021-1-3 12:16:19 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
  希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本。
思想:
将待排序数组按照步长gap举行分组,然后将每组的元素使用直接插入排序的方法举行排序;每次将gap折半减小,循环上述操纵;当 gap=1时,使用直接插入,完成排序。同样的:从上面的形貌中我们可以发现:希尔排序的总体实现应该由三个循环完成:第一层循环:将gap依次折半,对序列举行分组,直到gap=1第二、三层循环:也即直接插入排序所需要的两次循环。
  
[img=75%,75%]https://img-blog.csdnimg.cn/img_convert/4263c4ada0679847c3038c962b82b7b1.png[/img]
代码

移位法
  1.     public static void shell(int[] arr) {        int index = 0;//纪录当前分组的元素索引        int indexVal = 0;//元素值        for (int gap = arr.length / 2; gap > 0; gap /= 2) {//举行分组            for (int i = gap; i < arr.length; i++) {//对每个分组举行遍历                index = i;                indexVal = arr[i];                while (index - gap >= 0 && arr[index - gap] > indexVal) {                    arr[index] = arr[index - gap];//向后移动                    index -= gap;//按步长向后移动                }                arr[index] = indexVal;//移动完成后,当前位置就是indexVal所需要存放的位置            }        }    }       /**     * 互换元素     *     * @param arr     * @param i     * @param j     */    public static void exchage(int[] arr, int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }
复制代码
互换法
  1. /**     * 互换法     *     * @param arr     */    public static void shellSoer(int[] arr) {        for (int gap = arr.length / 2; gap > 0; gap /= 2) {//举行分组            //遍历每个分组            for (int i = gap; i < arr.length; i++) {                //对一个分组的元素举行排序                for (int j = i - gap; j >= 0; j -= gap) {                    if (arr[j] > arr[j + gap]) exchage(arr, j + gap, j);//满足条件举行互换                }            }        }    }
复制代码
互换法和位移法速度比力:


来源:https://blog.csdn.net/qq_44895397/article/details/112000060
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )