希尔排序

2021-01-06 12:28

阅读：677

标签：组元有序 shellSort 增量长度 increase tps 分组 font

希尔排序

概念

　　　希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

步骤

　　　　在网上看到一个很不错的例子，分享一下：https://blog.csdn.net/qq_39207948/article/details/80006224

　　　　首先，将数组中的元素按下标间距为4分组，即array[0]和array[4]一组，array[1]和array[5]一组，以此类推，间距4就被称为增量；第一个增量一般是数组长度的一半

　　　　　对分好的组进行插入排序，各组就变得有序了；并按照小元素在前面，大元素在后面重新排列数组

　　　　　　技术图片

　　　　　然后，将增量变为原来的一半，也就是2，再重新分组：

　　　　　对新分组进行插入排序，并重新排列数组：

　　　　　　技术图片

　　　　　再将增量变为原来的一半，也就是1；当增量为1时，也意味着希尔排序到了最后一步：

　　　　技术图片

　　　　　增量为1时就只剩下一个组了，直接对该组进行插入排序，这一组的数据也就完成了排序

Java代码实现

public class ShellSort {
    public void shellSort(Integer arr[]){
        //先判断数组元素是否只有一个以下，若只有一个就不用排序
        if(arr.lengthreturn;
        //定义增量
        int increase = arr.length/2;
        //判断增量是否到1了,没到1就进行排序
        while(increase>=1){
            for(int i=0;i){
                //进行插入排序
                for(int j=i;jincrease){
                    if(arr[j]>arr[j+increase]){
                        int temp = arr[j];
                        arr[j] = arr[j+increase];
                        arr[j+increase] = temp;
                    }
                }
            }
            //一次增量完成，设置新的增量
            increase = increase/2;
        }
    }
    public static void main(String[] args) {
        Integer arr[] = {9,1,3,5,6,4};
        System.out.println("排序前的数组："+Arrays.toString(arr));
        ShellSort shellSort = new ShellSort();
        shellSort.shellSort(arr);
        System.out.println("排序后的数组："+Arrays.toString(arr));
        //最终输出结果:
        //排序前的数组：[9, 1, 3, 5, 6, 4]
        //排序后的数组：[1, 3, 4, 5, 6, 9]
    }

}

希尔排序

标签：组元有序 shellSort 增量长度 increase tps 分组 font

原文地址：https://www.cnblogs.com/javaisbest/p/12977290.html

上一篇：[LeetCode] 974. 和可被 K 整除的子数组！！！

下一篇：springmvc返回json数据时，日期数据显示为数字的解决方式

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：希尔排序
文章链接：http://soscw.com/index.php/essay/40480.html

亲，登录后才可以留言！

希尔排序

评论

热门文章

推荐文章

最新文章

置顶文章