米鼠商城

多快好省,买软件就上米鼠网

最新项目

人才服务

靠谱的IT人才垂直招聘平台

排序算法二 -- 希尔排序

  • Elli_ON
  • 2
  • 2021-04-14 10:41

概述

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;

这个结论很明显,如果一个数组大部分元素都有序,那么数组中的元素自然不需要频繁地进行比较和交换。

  • 在元素数量较少的情况下,插入排序的工作量较小

这个结论更加显而易见,插入排序的工作量和n的平方成正比,如果n比较小,那么排序的工作量自然要小得多

也就是说:如果我们对数据做一些 “预处理”,使得原始数组的大部分元素变得有序,那么我们再使用插入算法进行排序,那么排序的效率将会大大提高。希尔排序正事基于这种思路实现的。

举个栗子

这是我们现在拿到的原始数组:

第一轮,我们取总长度的一半,也就是4,作为跨度,这样两两一组,总共事4组:

接下来,我们让每组元素进行独立排序,排序方式用直接插入排序即可。由于每一组的元素数量很少,只有两个,所以插入排序的工作量很少。每组排序完成后的数组如下:

这样一来,仅仅经过几次简单的交换,数组整体的有序程度得到了显著提高,使得后续再进行直接插入排序的工作量大大减少。这种做法,可以理解为对原始数组的“粗略调整”。 但是这样还不算完,我们可以进一步缩小分组跨度,重复上述工作。把跨度缩小为原先的一半,也就是跨度为2,重新对元素进行分组,一共两组:

接下来,我们继续让每组元素进行独立排序,排序方式用直接插入排序即可。每组排序完成后的数组如下:

最后,我们把分组跨度进一步减小,让跨度为1,也就等同于做直接插入排序。经过之前的一系列粗略调整,直接插入排序的工作量减少了很多,排序结果如下:

让我们重新梳理一下分组排序的整个过程:

代码实现:

    public static int[] sort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int step = arr.length/2;
        for(;step>0;step/=2){
            for(int i=step;i<arr.length;i++){
                int temp = arr[i];
                int j=i;
                for(;j>=step && temp<arr[j-step];j-=step){
                    //符合条件往后移
                    arr[j] = arr[j-step];
                }
                arr[j] = temp;
            }
        }
        return arr;
    }

算法分析:

  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(1)


这里给大家推荐一个在线软件复杂项交易平台:米鼠网 https://www.misuland.com

米鼠网自成立以来一直专注于从事软件项目人才招聘软件商城等,始终秉承“专业的服务,易用的产品”的经营理念,以“提供高品质的服务、满足客户的需求、携手共创双赢”为企业目标,为中国境内企业提供国际化、专业化、个性化、的软件项目解决方案,我司拥有一流的项目经理团队,具备过硬的软件项目设计和实施能力,为全国不同行业客户提供优质的产品和服务,得到了客户的广泛赞誉。



如有侵权请联系邮箱(service@misuland.com)

猜你喜欢

评论留言