十大常用的排序算法之希尔排序 C#实现
发布日期:2021-07-22 10:54:33
浏览次数:5
分类:技术文章
本文共 1641 字,大约阅读时间需要 5 分钟。
十大常用的排序算法之希尔排序 C#实现
昨天讲了一下,今天让我们看看他的升级版———“希尔排序”。
算法描述 什么是希尔排序呢?希尔排序,英文名“Shell Sort”。它基于插入排序的算法思想,增加了一个“增量”(或者说是“每组元素之间的间隔”)的概念。将一组数据按下标的一定“增量”分组,对每组使用直接插入排序算法排序。每一次循环过后,“增量”会变小,每个分组中的元素会增加。当增量减小到1时,所有元素被分为一组,排序结束。举个例子:现在我们有一个这样的无序数组。
数组的长度为10,增量=数组长度 / 2 = 5,按照增量分为以下五组。
每组进行插入排序,结果如下。
增量=增量/ 2 = 2,按照增量分为以下两组。 每组进行插入排序,结果如下。 可以看到数据已经趋近于一个有序数组了。增量继续减少,增量=增量/2=1,所有数据被分成了一组。插入排序,结果如下。
数组已经变为了有序数组,排序结束。整体排序过程如下。原数组: [10] [30] [50] [7] [6] [11] [8] [35] [24] [27]
排序开始
第一轮排序(增量5):[10] [8] [35] [7] [6] [11] [30] [50] [24] [27]
第二轮排序(增量2):[6] [7] [10] [8] [24] [11] [30] [27] [35] [50]
第三轮排序(增量1):[6] [7] [8] [10] [11] [24] [27] [30] [35] [50]
排序结束
算法实现 C#
//希尔排序 public static int[] ShellSort(int[] arr) { int n = arr.Length; //定义增量gap,随着每轮循环减小,小于等于0是退出循环 for(int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { //待插入元素 int inserted = arr[i]; //j所指向的是待比较元素 int j = i - gap; //如果j所指向的待比较元素下标大于或等于0时,并且待插入的元素小于待比较的元素时,待比较元素向后移动 //然后继续向左遍历(j-gap),那么空出来的位置就是(j+gap) while (j>=0&&inserted < arr[j]) { arr[j + gap] = arr[j]; j -= gap; } //直到不满足条件时结束循环,将元素插入 arr[j + gap] = inserted; } } return arr; }
算法分析
希尔是不稳定排序(),希尔排序和的实现上并没有太大的区别,只不过多了一个gap。但是在数据量很大的情况下,希尔排序移动的次数,明显小于插入排序移动的次数,排序的速度更快。平均时间复杂度为O(nlogn),空间复杂度O(1)。转载地址:https://blog.csdn.net/m0_56500170/article/details/115278229 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月28日 02时25分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java选择路径窗口_Java实现选择电脑路径的方法
2019-04-21
冒泡排序面向对象java_所谓的面向对象实现的冒泡排序
2019-04-21
java编写roguelike_RogueLike地牢生成算法Unity实现
2019-04-21
java并发编程指南博客_Java并发编程-synchronized指南
2019-04-21
java怎么中断阻塞状态_java并发编程()阻塞方法与中断方法
2019-04-21
java zlib 位运算_位运算入门:找出一个二进制数的最右端的第一个1;计算一个二进制数中1的个数;找出数组中唯一一个出现次数为奇数的数;找出数组中唯二两个出现次数为奇数的数...
2019-04-21
java lua热更新_lua热更新学习
2019-04-21
php apc.dll下载,PHP之APC缓存详细介绍 apc模块安装
2019-04-21
html贝塞尔曲线在线,贝塞尔曲线的一些事情_html/css_WEB-ITnose
2019-04-21
Java前台显示近20天的东西_第十次课:前台首页设计及显示商品信息
2019-04-21
java开发web网站的路由设计_理解Web路由(浅谈前后端路由与前后端渲染)
2019-04-21
excel如何把顺序倒过来_在excel中怎么使文字颠倒顺序反过来显示呢?
2019-04-21
脚本语言php是什么意思,PHP脚本语言
2019-04-21
matlab数学规划模型,数学规划模型
2019-04-21