十大常用的排序算法之希尔排序 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Unity 3D Generic动画类型,对于应用RootMotion的设置
下一篇:无重复字符的最长字串

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月28日 02时25分59秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java选择路径窗口_Java实现选择电脑路径的方法 2019-04-21
java 图像渐变_Java基础之在窗口中绘图——渐变填充(GradientApplet 1) 2019-04-21
冒泡排序面向对象java_所谓的面向对象实现的冒泡排序 2019-04-21
proto 客户端 JAVA_Kubernetes官方java客户端之五:proto基本操作 2019-04-21
java编写roguelike_RogueLike地牢生成算法Unity实现 2019-04-21
java ajax 修改数据库数据库数据库_AJAX 自学练习 无刷新提交并修改数据库数据并显... 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
script执行php文件_php命令行(cli)下执行PHP脚本文件的相对路径的问题解决方法... 2019-04-21
apache 2.4 php5.4_apache2.4+php5.4+my sql 5.6,网站经常无故不能访问 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
脚本语言php是什么意思,PHP脚本语言 2019-04-21
matlab数学规划模型,数学规划模型 2019-04-21