- 综合排序
- 最热优先
- 最新优先
- 来自专栏C++打怪之路
排序2：希尔排序（缩小增量排序）
上一期，我们介绍了直接插入排序。 这一期，我们来介绍希尔排序的底层逻辑和代码实现。 ---- 目录 希尔排序的基本思想 单趟的实现 整个排序的实现 总结 ---- 希尔排序的基本思想 先选定一个整数gap，把待排序文件中所有记录分成gap个 组，所有距离为gap的记录分在同一组内 2、每一组从后往前遍历排序。 3、与后面一个间隔为gap的数比较。 整个排序的实现 核心思想： 1、gap递减，缩小排序组数，最终到gap = 1的时候，就是一次直接插入排序了。 2、齐头并进。 而希尔排序在排序中也是不稳定的（不稳定：即有可能因为某部分的有序破坏原先的已经变为有序的部分）。
55920编辑于 2023-03-31 - 来自专栏云霄雨霁
排序----希尔排序
上一篇：插入排序 希尔排序的思想是：使数组中任意间隔为h的元素都是有序的。这样的数组成为h有序数组。换句话说，一个h数组就是h个互相独立的有序数组 编织在一起组成的数组。 实现希尔排序的一种方法是对于每个h,使用插入排序将h个子数组独立地排序。然后按某种次序递减h,可以实现数组整体排序。这里出现两个问题：为什么使用插入排序而不是选择排序？按哪种次序递减h? 希尔排序是对直接插入排序的改进，它权衡了子数组的规模和有序性。它避免了直接插入排序主键最小的元素正好在数组的尽头，要将它挪动到正确的位置需要移动次数很多的问题。 希尔排序的算法性能不仅取决于h,还取决于h之间的数学性质，比如它们的公因子等。 希尔排序的用时是次平方级别的，目前发现希尔排序最坏情况也达不到平方级别，是N^1.5次方。 ” } 从希尔排序可以发现，我们对插入排序稍微改动，就在效率上取得了极大的提升，算法的魅力正在于此。
1.1K00发布于 2018-05-30 - 来自专栏若尘的技术专栏
排序——希尔排序
希尔排序（基于逐趟缩小增量） 基本思想 先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 [在这里插入图片描述] 算法实现 void ShellSort(SqList &L, int dlta[], int t){ // 按增量序列dlta[0…t-1]对顺序表L作Shell排序 for (k = 0; k < t; k++) ShellInsert(L, dlta[k]); // 增量为dlta[k]的一趟插入排序 } void ShellInsert(SqList &L, int dk){ // 对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子 for(i = dk + 1; i <= L.length; i++){ // 开始将r[i] 插入有序增量子表 dk] = r[j]; // 关键字较大的记录在子表中后移 r[j + dk] = r[0]; // 在本趟结束时将r[i]插入到正确位置 } } } 算法分析 时间复杂度： O（n3/2）
997105发布于 2021-06-30 - 来自专栏趣谈编程
希尔排序
希尔排序（ShellSort）是以它的发明者Donald Shell名字命名的，希尔排序是插入排序的改进版，实现简单，对于中等规模数据的性能表现还不错 排序思想 前情回顾：直接插入排序（对插入排序不熟悉的强烈建议先阅读此文 其实希尔排序就可以实现这个效果 希尔排序是怎么做的呢？ ? ? 一尘 ? 慧能 ? 然后缩小增量为上个增量的一半:2，继续划分分组，此时，每个分组元素个数多了，但是，数组变的部分有序了，插入排序效率同样比较高 ? 同理对每个分组进行排序（插入排序），使其每个分组各自有序 ? 同理，对这仅有的一组数据进行排序，排序完成 希尔排序真厉害啊，同时构造出两个特殊条件以达到高效插入 ? ? 一尘 ? 慧能 ? 恩恩，这就是希尔排序的精华所在 排序代码 ? 慧能 ? ,每次都通过减半来得到新的增量 希尔排序的复杂度和增量序列是相关的 {1,2,4,8,...}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n^2) Hibbard提出了另一个增量序列
53660发布于 2018-06-13 - 来自专栏c++与qt学习
希尔排序
希尔排序是对插入排序的改进算法，主要针对插入排序需要在数组基本有序或者数量较少时才会效率较高的这两个限制进行改进 希尔排序基本思想 希尔排序的过程图解 如何分割待排序记录？ 子序列内如何进行直接插入排序？ 算法描述： 直接插入排序个希尔排序的对比 时间性能 手绘图解加上完整代码 下面就是重复上述步骤，这里不做演示了 #include<iostream> using namespace std; //希尔排序 void shellSort(int arr[],int len) { for (int d=len/2; d >= 1; d/=2) { for (int i = d temp; } } } void test() { int arr[] = { 40,25,49,25,16,21,8,30,13 }; shellSort(arr,9); cout << "希尔排序后
25020编辑于 2022-05-05 - 来自专栏技术面面观
希尔排序
希尔排序（ShellSort）是以它的发明者Donald Shell名字命名的，希尔排序是插入排序的改进版，实现简单，对于中等规模数据的性能表现还不错 排序思想 前情回顾：直接插入排序（对插入排序不熟悉的强烈建议先阅读此文 其实希尔排序就可以实现这个效果 希尔排序是怎么做的呢？ ? ? 一尘 ? 慧能 ? 然后缩小增量为上个增量的一半:2，继续划分分组，此时，每个分组元素个数多了，但是，数组变的部分有序了，插入排序效率同样比较高 ? 同理对每个分组进行排序（插入排序），使其每个分组各自有序 ? 同理，对这仅有的一组数据进行排序，排序完成 希尔排序真厉害啊，同时构造出两个特殊条件以达到高效插入 ? ? 一尘 ? 慧能 ? 恩恩，这就是希尔排序的精华所在 排序代码 ? 慧能 ? ,每次都通过减半来得到新的增量 希尔排序的复杂度和增量序列是相关的 {1,2,4,8,...}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n^2) Hibbard提出了另一个增量序列
53410发布于 2019-12-12 - 来自专栏哈雷彗星撞地球
希尔排序
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 然后，再取一个小于d1的整数d2，作为第二次的增量，再次对[0,d2,2d2,3d2....],[1,1+d2,1+2d2,....]，......等数组做插入排序。 ...... 2.再将原数组按照增量d2拆分成多个子数组，然后再在子数组内做增量排序。 3....... 4.直到增量d为1时，整个要排序的数组被分成一组，排序完成。 希尔排序的时间复杂度与增量序列的选取有关，Hibbard增量的希尔排序的时间复杂度为O(n3/2)，希尔排序时间复杂度的下界是n*log2n。 希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择，但是比O(n2)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。
78840发布于 2019-05-15 - 来自专栏xingoo, 一个梦想做发明家的程序员
希尔排序
使用希尔增量时排序的最坏为：O(n^2); 代码如下： 1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 template <typename Comparable> 5 void shellsort(vector<Comparable> & a) 6 { 7 for(int gap = a.size()/2; gap > 0; gap /= 2) 8 for(int i = gap; i < a.size() ; i++) 9 { 10 Comparable 20 vector<int> ivec; 21 ivec.push_back(1); 22 ivec.push_back(9); 23 ivec.push_back(2)
68970发布于 2018-01-17 - 来自专栏软件开发 -- 分享 互助 成长
希尔排序
1、希尔排序介绍 希尔排序是对直接插入排序算法的一种改进，当记录较少或者记录本身基本有序的时候直接插入排序的优势非常明显，所以希尔排序就是通过人为的创造这两个条件，然后进行插入排序，基本思想是设置一个增量 引用一个别人的博文的例子“经典排序算法 - 希尔排序Shell sort ” 准备待排数组[6 2 4 1 5 9] 首先需要选取关键字,例如关键是3和1(第一步分成三组,第二步分成一组),那么待排数组分成了以下三个虚拟组 1 6] [2 5]2与5不动还是[2 5] [4 9]4与9不动还是[4 9] 第一趟排序状态演示: 待排数组:[6 2 4 1 5 9] 排后数组:[1 2 4 6 5 9] 第二趟关键字取的是1, ,就是4后边,6前边 后边的也不用改,所以排序完毕 顺序输出结果:[1 2 4 5 6 9] 2、希尔排序的关键是如何取关键字,因为其它内容与插入排序一样 好的增量序列的共同特征: ① 最后一个增量必须为 +1)-1 (t、k有一定的范围)的时候可以获得不错的效果公式参见大话数据结构p395 下面为C++的shell排序实现： // 希尔排序.cpp : 定义控制台应用程序的入口点。
74080发布于 2018-02-05 - 来自专栏JavaEE
排序算法 --- 希尔排序
一、排序思想 之前说到插入排序，希尔排序就对其进行了一个优化，优化的思路是： 对待排序列进行分组，组数为gap = arr.length / 2； 对每一组进行插入排序，然后再进行分组，gap = gap / 2； 再对每一组进行插入排序，直到最后组数为1，再进行最后一次插入排序即可； ---- 欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新 9$ 此时，gap = gap / 2 = 2 / 2 = 1，组数为1，所以不用分了，对这一组再进行插入排序，那么整个排序过程就完了。 二、代码实现 关于希尔的代码实现，网上很多花里胡哨的答案，什么交换法位移法之类的，其实不要想得那么复杂。 刚才说了，希尔排序的主要思想就是分组，对每一组分别进行插入排序，那代码就简单了，就是这分组里面将之前插入排序的代码拷过来稍微改改就行了。
75431发布于 2020-10-10 - 来自专栏学习C/++
【排序算法】希尔排序
希尔排序( 缩小增量排序 ) 希尔排序是一种经典的排序算法，它通过多次插入排序的方式，以及逐步缩小增量的策略，实现对数据的高效排序，希尔排序法又称缩小增量法。 缩小增量的过程 希尔排序的另一个关键点是逐步缩小增量的过程。初始时，增量的值通常为数组长度的一半。随着排序的进行，增量逐步减小，直到增量为1，完成最后一次排序。 排序步骤 希尔排序的排序步骤可以分为以下几个阶段： 分组排序：初始时，根据设定的增量将数据分成若干组，对每组数据进行插入排序，使得每组数据都部分有序。 , int n) { int gap = n; while (gap > 1) { //gap /= 2; gap = gap/3 + 1; for (int i = 0; i < ： 希尔排序是对直接插入排序的优化。
53710编辑于 2024-03-30 - 来自专栏静默虚空的博客
排序四 希尔排序
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。 所以，希尔排序是不稳定的算法。 // 减小增量 } } 算法分析 希尔排序的算法性能 [图片] 时间复杂度 步长的选择是希尔排序的重要部分。 这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。 算法稳定性 由上文的希尔排序算法演示图即可知，希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。 直接插入排序和希尔排序的比较 直接插入排序是稳定的；而希尔排序是不稳定的。
1.2K90发布于 2018-01-05 - 来自专栏从零开始的Code生活
希尔排序
希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。 实现希尔排序的一种方法是对于每个h，用插入排序将h个子数组独立地排序。 只需要在插人排序的代码中将移动元素的距离由1改为h即可。这样，希尔排序的实现就转化为了一个类似于插人排序但使用不同增量的过程。 希尔排序为插入排序高级版，先把几个部分的数组用插入排序排好，然后再把这几个分散数组排序成有序数组。 确定一个增量h（h可以是数组总长/3 or /2），每次循环完增量变小直到为1，每次把分散的数组整合成一个大的有序数组，直到增量为1时，整个数组排序完成。 void shellsort(int a[], int m) { int h = m / 2; //确定增量h for (h; h >= 1; h /= 2) //每次增量变小
32910编辑于 2022-01-13 - 来自专栏Vegout
希尔排序
希尔排序 如果上一篇初级排序算法中的插入排序你已经熟悉，那么今天的这个希尔排序对你来说就要简单一些。希尔排序，就是使用不同增量进行一遍一遍的插入排序的排序算法。首先，增量是什么？ 插入排序中比较的是array[j]和array[j-1]，所以说，希尔排序就是使用不同增量的插入排序算法。当然，也由于希尔排序可以使用不同增量，于是透彻的理解希尔排序的性能仍旧是个巨大的挑战。 今天我们代码中使用的是1,24,13,40,121,364…这一个增量序列，其实，还有其他别的增量序列可以供我们选择,比如1,2,4,8,16….. 希尔排序比之前初级排序算法中的排序算法都要快，并且，数组越大，优势越大。但为什么呢？从数学方面的证明还是等专家们去做吧，我只能举个栗子。 比如有一个特别长的整型数组，特别小的数排在了最后边，插入排序的话它就需要一点一点的挪到前面，而希尔排序则是跳过来的，一次跳多远呢？
59830发布于 2019-07-03 - 来自专栏python-爬虫
希尔排序
一.思想 希尔排序是一种分组插入排序算法。 首先取一个整数d1=n/2，将元素分为d1个为一组，每组相邻量元素之间距离为d1，两组数据一一进行对比按大小,从新分配两组 如[1,3,0,2] 第一次排序后变成[0,2,1,3] 取第二个整数d2=d1 /2，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序。 按上面那个简单例子走第二次排序为 [0,2,1,3]按间隔1进行对比第一次然后依次变成 0与2比,0比2小顺序不变 [0,2,1,3] 2与1比,1比2小1去前面 [0,1,2,3] 依次类推...全部走完就是排好了 [0,1,2,3] 二.代码 这是网上找的精简后的代码,我自己撸的和屎一样很乱 def shell_sort(li): gap = len(li)//2 while gap>0:
32230编辑于 2022-05-09 - 来自专栏AI那点小事
希尔排序
概述 由于之前的冒泡排序和插入排序效率低平均复杂度为O(n^2)，那么为了加快排序效率，希尔排序就这样被提出来了。 因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比插入排序和冒泡排序的效率高。 那么对于增量的选择各种各样，选择的好坏会直接影响希尔排序的效率。 首先先看个坏例子 那么好的增量必须前后不互质，那么下面有几个著名增量序列： 那么基于Sedgewick增量序列的希尔排序算法如下： //希尔排序 void Shell_Sort( size) { for(int i = 0 ; i < size ; i++){ cout<<data[i]<<" "; } cout<<endl; } //希尔排序 ："<<endl; Print(data,size); cout<<"希尔排序后："<<endl; Shell_Sort(data,size); Print(data,size
44420编辑于 2022-06-15 - 来自专栏数据结构与算法分享
希尔排序
最近在全面学习数据结构，常用算法记录：希尔排序，基本思想是选定一个增量 d<nd 的元素为一组），然后在各个子序列内进行插入排序，完成后缩小增量 d'(d'<d)d = 1 为止，此时就成了标准的插入排序 ，但此时大部分元素已经有序，只需要少量操作，甚至不用操作即可完成排序。 该排序算法为不稳定排序。 希尔排序还是比较绕的，需要多看看，多画一画。 最坏时间复杂度：O(n^2)n 在某范围内可达：O(n^{1.3})目前无法用数学手段证明确切的时间复杂度。 return 0; } void shellSort(int arr[], int n) { int d, i, j; //arr[0]为暂存单元 for (d = n / 2; d > 0; d /= 2) //d为步长 { for (i = d + 1; i <= n; i++) //从子表中第二个元素开始 if(arr
42310编辑于 2022-09-19 - 来自专栏hotarugaliの技术分享
希尔排序
简介 希尔排序又称缩小增量排序，其也属于插入排序类算法。相较于一般的插入算法、折半插入算法、2-路插入算法以及表插入算法，希尔排序在时间效率上更加优秀。 2. 伪代码 ShellSort(A, D) { // 按增量序列 D 对数组 A 进行希尔排序 for i = 1 to D.length // 以下类比与一般的插入排序， 常用的增量序列有： 希尔排序时间复杂度 。 希尔排序时间复杂度 。 希尔排序时间复杂度 。 希尔排序时间复杂度 。 希尔排序时间复杂度 。 希尔排序时间复杂度 。 ， , 递减到 0（即连续递减到 1 的光滑数 ） 希尔排序时间复杂度 。 希尔排序是不稳定的、原址的。 不稳定原因在于希尔排序中不同段交换元素时会打乱相等元素初始的相对位置。 4.
31710编辑于 2022-03-01 - 来自专栏JusterZhu
希尔排序
1.概要 希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，他是简单插入排序经过改进之后的一个更高效的版本，也成为缩小增量排序。 希尔排序算法基本思想 希尔排序是吧记录按下标的一定增量分组，对每组使用直接插入排序算法排序：随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 2.详细内容 public class ShellSort { public static void Sort(int[] arr) { int gap = arr.Length / 2; while (gap > 0) { for (int i = gap; Program { static void Main(string[] args) { int[] array = { 8,9,1,7,2,3,5,4,6,0
33720编辑于 2022-12-07 - 来自专栏xingoo, 一个梦想做发明家的程序员
希尔排序
希尔排序的时间复杂度，最好的情况下仍然是正序时，可达到O(n),平均复杂度为O(nlogn)。 算法思想： 采用跳跃式处理数组，使得数组粗粒度的实现基本有序。 在进行细粒度的处理，最终使得网络在跳越数为1时，实现基本有序的排序，以减少插入排序的复杂度。 } 全部代码： #include <stdio.h> #include <stdlib.h> #include <time.h> int arrtest1[10] = {3,4,7,8,0,9,1,2,6,5 }; int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9}; int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0}; void copy(int ("first test:%d\n",end-start); start = clock(); for(i=0;i<100000;i++){ copy(arrtest2,
55550发布于 2018-01-17
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号