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

希尔排序 java实现

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

希尔排序 java实现

先说思路

先把数组分成一个个的小的数组,在数组内排序后,在划分较大一点的数组,在数组内再排序,最后成为一个数组

希尔的目的是防止插入排序的最后是最小的数,要移动全部的数组导致的浪费,所以尽可能的让每个小组的小数在前面,这样移动的时候不至于移动太多次

希尔有两种实现方式

1.交换法 不推荐

时间消耗极高

    //交换式
    public static void shell1(int[] arr){
        int temp = 0;
        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]){
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }

问题在于每次比较只要满足条件都会交换,浪费时间

2。移位法 推荐

实质是先分组再插入,记录这个数字,然后进行比较,如果不满足就依次覆盖,最后满足或者跳出循环后再把记录的数字赋值

    //移位法
    public static void shell2(int[] arr){
        for (int gap = arr.length/2;gap > 0 ; gap /= 2){
            //插入排序
            for (int i = gap ; i < arr.length;i++){
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]){
                    while (j - gap >= 0 && temp < arr[j - gap]){
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
            System.out.println("==============");
            System.out.println(Arrays.toString(arr));
        }

    }

时间消耗大大降低

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

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

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