排序算法——希尔排序

傷城~ 2022-06-12 00:20 237阅读 0赞

## 前言 ##

希尔排序又称缩小增量排序，是时间效率较高的插入排序方法。

算法的基本思想：先确定一个增量d（也叫间隙gap），然后按照增量的倍数所对应的数组下标值，从待排序序列中抽取数据元素组成若干子序列，然后对子序列分别做直接插入排序，这样的操作过程就是一趟希尔排序。进行下一趟希尔排序时，先确定一个更小的增量，然后再作以上操作，直到增量为1，做最后一次直接插入排序，由于序列基本已经有序，此时只需要很少的比较和移动就可以获得有序序列。

对于图文介绍大家个可以参考这篇*[博客][Link 1]*。

## 1. 编码 ##

template<typename T> struct Disp
    {
        void operator()(T value)
        {
            cout << value << "\t";
        }
    };
    
    void ShellSort(std::vector<int>& vec)
    {
        int len(vec.size());
        if(len == 0) return;
        cout << "display origin array:" << endl;
        for_each(vec.begin(), vec.end(), Disp<int>());  //打印原始的数据
    
        int gap(len/2); //获得初始间隔大小
        for(; gap>0; gap/=2)
        {
            for(int j=gap; j<len; ++j)
            {
                int temp = j;
                while(temp-gap>=0 && vec[temp]<vec[temp-gap])    //插入排序采用交换法
                {
                    int temp_val = vec[temp];
                    vec[temp] = vec[temp-gap];
                    vec[temp-gap] = temp_val;
                    //std::swap(vec, temp, temp-gap);
                    temp -= gap;
                }
            }
        }
    
        cout << "\narray sorted:" << endl;
        for_each(vec.begin(), vec.end(), Disp<int>());
    }

[Link 1]: http://www.cnblogs.com/chengxiao/p/6104371.html

发表评论取消回复

表情：

评论列表（有 0 条评论，237人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法 - 希尔排序

基本思路希尔排序也是一种插入排序，又称缩小增量排序，在效率上教其他插入排序有较大的改进。 ① d=n/2 ②将排序序列分为d个组，在各组内进行直接插入排序 ③递减

不念不忘少年蓝@/ 2023年08月17日 16:43/ 0 赞/ 56 阅读

相关【排序算法】希尔排序

> 本篇文章来聊一聊希尔排序。基本思想上篇文章我们学习了折半插入排序，该排序算法的原理是在顺序插入查找插入过程中使用折半查找法从而提高插入效率，为此，我们可以思考一

阳光穿透心脏的1/2处/ 2023年07月19日 10:32/ 0 赞/ 19 阅读

相关排序算法-希尔排序

> 1.希尔排序将待排序数组按照步长进行分组，然后将每组的元素利用直接插入排序的方法进行排序，每次将步长折半减小，gap=1时，利用直接插入完成排序。 1）第一层循环将g

深藏阁楼爱情的钟/ 2023年06月13日 11:22/ 0 赞/ 4 阅读

相关【排序算法】希尔排序

排序动图 ![aHR0cHM6Ly95dXUtYmxvZy5vc3MtY24tc2hlbnpoZW4uYWxpeXVuY3MuY29tL3NoZWxsU2hvcnQuZ2

深藏阁楼爱情的钟/ 2023年02月19日 05:30/ 0 赞/ 17 阅读

相关【排序算法】- 希尔排序

文章目录 1 简单插入排序存在的问题 2 希尔排序法介绍 3 希尔排序法基本思想 4 希尔排序法的示意图 5 希尔排序法应用实例: 1

淩亂°似流年/ 2022年12月20日 01:52/ 0 赞/ 136 阅读

相关算法——希尔排序

强烈推荐一个大神的人工智能的教程：[http://www.captainbed.net/zhanghan][http_www.captainbed.net_zhanghan]

￡神魔★判官ぃ/ 2022年07月16日 06:48/ 0 赞/ 210 阅读

相关排序算法——希尔排序

前言希尔排序又称缩小增量排序，是时间效率较高的插入排序方法。算法的基本思想：先确定一个增量d（也叫间隙gap），然后按照增量的倍数所对应的数组下标值，从待排序序列中

傷城~/ 2022年06月12日 00:20/ 0 赞/ 238 阅读

相关排序算法：希尔排序

一、前言希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。希尔排序，也称递减增量排序算法，以其设计

柔光的暖阳◎/ 2022年04月05日 09:47/ 0 赞/ 340 阅读

相关排序算法——希尔排序

排序算法——希尔排序 > 希尔排序：是直接插入排序算法的一种更高效的改进版本。又称“缩小增量排序”（Diminishing Increment > Sort）。希尔排

水深无声/ 2021年11月09日 00:54/ 0 赞/ 345 阅读

相关算法——希尔排序

文章目录前言介绍特点基本思想实现总结代码实现拓展：克努特序列前言为了学习面试中常常要考察到的希

柔光的暖阳◎/ 2021年11月05日 06:56/ 0 赞/ 361 阅读