搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 程序猿张先森 > 排序算法之插入排序(直接插入、希尔排序)

排序算法之插入排序(直接插入、希尔排序)

程序猿张先森 2018-11-01

前言

一个好的排序算法对于程序的优化会有很大的提升,虽然在许多语言的类库中就存在了N种排序方法,但是只有在了解了每一种排序算法后才能更好的在实际中运用这些算法。这里我主要说明插入排序中的直接插入以及希尔排序的实现。

直接插入

直接插入排序是最简单的排序算法之一。对于直接插入排序,它始终维护着一个有序序列,在每一次插入操作时都将元素插入到这个有序序列对应的位置上。

对于一个待排序序列:3 1 4 8 6 5,插入排序的步骤如下:


该算法也比较简单:
public void insertionSort(T[] array){
        int j = 0;
        for(int i=1;i<array.length;i++){
            T tmp = array[i];
            for(j=i;j>0 && tmp.compareTo(array[j-1])<0;j--){
                array[j] = array[j-1];
            }
            array[j] = tmp;
        }
    }

可以看出,该算法从待排序的序列第二位开始始终维护着位置0到位置i为一个排过序的状态。并且在进行元素交换过程中,采用移动法的方式,避免了多次的元素交换操作。

时间复杂度:O(N²) 空间复杂度:O(1)

希尔排序

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(N²)的第一批算法之一。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个序列恰被分成一组,算法便终止。

对于一个待排序序列:3 1 4 8 6 5 2 7,希尔排序的步骤如下:

希尔排序代码如下:

public void shellSort(T[] array){
        int j;
        for(int gap = array.length/2;gap>0;gap/=2){
            for(int i=gap;i<array.length;i++){
                T tmp = array[i];
                for(j = i;j>=gap && tmp.compareTo(array[j-gap]) < 0;j -= gap){
                    array[j] = array[j - gap];
                }
                array[j] = tmp;
            }
        }
    }

在希尔排序中,增量的选择尤为重要,一个好的增量对于性能的提升有很大帮助,常用以及希尔建议的增量序列为:gap = (array.length)/2。

在代码的第4行,我们从增量大小的数组下标位置开始向前进行插入排序。

时间复杂度:O(N²) 空间复杂度:O(1)

总结

对于直接插入排序以及希尔排序都是插入排序的一种,但是他们的最坏时间情形都会达到O(N²)。在对于元素的交换过程灵活的使用移动法,可以降低交换操作带来的时间开销。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《排序算法之插入排序(直接插入、希尔排序)》的版权归原作者「程序猿张先森」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注程序猿张先森微信公众号

程序猿张先森微信公众号:zhyocean1314

程序猿张先森

手机扫描上方二维码即可关注程序猿张先森微信公众号

程序猿张先森最新文章

精品公众号随机推荐