数据结构——希尔排序(详解)

这篇具有很好参考价值的文章主要介绍了数据结构——希尔排序(详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

呀哈喽,我是结衣
不知不觉,我们的数据结构之路已经来到了,排序这个新的领域,虽然你会说我们还学过冒泡排序。但是冒泡排序的性能不高,今天我们要学习的希尔排序可就比冒泡快的多了。

希尔排序

希尔排序的前身是插入排序,可以说希尔排序就是插入排序的优化。并且优化了很多。所以在讲希尔排序前我们要先学会插入排序,不然在后续学习希尔排序会比较的吃力。那么让我们先进入插入排序的教学吧。

插入排序

直接插入排序是一种简单的插入排序法,其基本思想是:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。
实际上我们玩扑克的时候就运用了插入排序的思想
数据结构——希尔排序(详解),数据结构,排序算法,算法
本来想放张插入排序动图的,可是放进来后它就不动了。。。
下面我们来讲解插入排序的特点:

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高
  2. 时间复杂度:O(N^2)(逆序情况)
    最好情况为O(N)(数组比较有序)(为希尔排序提供了思路)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

了解完了,我们就要开始代码讲解了:

void InsertSort(int* a, int n)
{
	for(int i = 0;i<n-1;i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end>=0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
			a[end + 1] = tmp;
		}
	}
}

思路:
在待排序的元素中,假设前end个元素已有序,现将第end+1个元素插入到前面已经排好的序列中,使得前end个元素有序。按照此法对所有元素进行插入,直到整个序列有序。但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止
数据结构——希尔排序(详解),数据结构,排序算法,算法
红色竖杆表示已经排好序列,绿色圈住的数字表示要插入到前面序列的数字。

希尔排序(缩小增量排序)

讲完插入排序,接下来就到了我们的重点了——希尔排序

希尔排序的思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。
在希尔排序中,我们要引入gap(间隔),我们来画图理解。
数据结构——希尔排序(详解),数据结构,排序算法,算法
当gap不为1时,我们可以把它看做为一个预排序,先把数组变成比较有序。然后当gap为1时就是直接插入排序了,因为插入排序对比较有序的数组排列效率更高,所以希尔排序就为先预排序,再直接插入排序。

预排序

再讲希尔排序的代码实现前,我们先来讲预排序。我们先定义一个长度为6的逆序数组{6,5,4,3,2,1}.再来假设gap为3。
我们知道插入排序再排逆序的数组时时间复杂度为最坏的情况。所以我们才要进行预排序。
数据结构——希尔排序(详解),数据结构,排序算法,算法
我们一组一组排
数据结构——希尔排序(详解),数据结构,排序算法,算法
经过预排序后数组,已经变得比较有序了,这对后面的直接插入排序是有好处的,提高效率。

int gap = 3;
	for(int i = 0;i<n-gap;i++)
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
			a[end + gap] = tmp;
		}
	}

这个只是一个预排序,和插入排序的思路大差不差,只是把改了一些细节。
看看打印结果
数据结构——希尔排序(详解),数据结构,排序算法,算法
和我们前面推算的相同。

希尔排序的代码实现

思路讲完了,预排序也讲完了。希尔排序终于要来了。在现实情况下,我们能知道gap为多少吗?像前面我的只排6个数据,gap=3还是可以的,但是如果我们要排一百万,一千万,一亿甚至更多的数呢?gap又要怎么算呢?我们要知道。gap越小预排序越接近有序,但也排的越慢。gap越大,预排序越不接近有序,但排的越快。但是我们找不到gap应该取多少,所以我们可以让gap等于一个随机的数但要越来越小直到gap=1进行插入排序。

void ShellSort(int* a, int n)
{
	int gap = n;
	// gap > 1时是预排序,目的让他接近有序
	// gap == 1是直接插入排序,目的是让他有序
	while (gap>1)
	{
		gap = gap / 3 + 1;//也可以写成gap/2.目的都是为了最后一次gap一定要为1.
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
				a[end + gap] = tmp;
			}
		}
	}
	
}

可能写起来比较麻烦,都是希尔排序的效率可是非常高度。它的效率略低于但接近快排和堆排,远高于插入排序,插入排序的效率又远高于冒泡排序。希尔排序的时间复杂度在下方。

希尔排序的特性

希尔排序的特性总结:文章来源地址https://www.toymoban.com/news/detail-755986.html

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就 会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的 希尔排序的时间复杂度都不固)
    下面我们来看严蔚敏老师和殷人昆老师的解释:
    《数据结构(C语言版)》— 严蔚敏
    数据结构——希尔排序(详解),数据结构,排序算法,算法
    《数据结构-用面相对象方法与C++描述》— 殷人昆
    数据结构——希尔排序(详解),数据结构,排序算法,算法

    数据结构——希尔排序(详解),数据结构,排序算法,算法

到了这里,关于数据结构——希尔排序(详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】:插入排序与希尔排序

    🔥 个人主页 : Quitecoder 🔥 专栏 : 数据结构与算法 欢迎大家来到初阶数据结构的最后一小节:排序 排序是一种将一组对象按照某种特定顺序重新排列的过程。在计算机科学中,排序是数据处理中非常基本且重要的操作,它可以帮助人们更有效地理解和分析数据。排序的顺序

    2024年03月18日
    浏览(39)
  • 【数据结构与算法】插入排序和希尔排序

      目录 一.插入排序  InsertSort 基本思想 动图演示  特性总结 二.希尔排序  ShellSort 基本思想 图例 特性总结 基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。 当插入第i(i=1)个元素

    2023年04月18日
    浏览(89)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(86)
  • 【数据结构与算法】直接插入排序和希尔排序

    进入了初阶数据结构的一个新的主题——排序。所谓排序,就是一串记录, 按照其中的某几个或某些的大小(一定的规则) , 递增或递减排列起来的操作 。 排序的 稳定性 :在一定的规则下,两个值相等的元素,在排序算法处理前后的相对位置是否发生变化,如果相

    2024年04月13日
    浏览(44)
  • 【数据结构】排序算法(一)—>插入排序、希尔排序、选择排序、堆排序

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.直接插入排序 2.希尔排序 3.直接选择排序 4.堆排序 本篇文章博主将介绍排序算法中的插入排序:直接

    2024年02月08日
    浏览(49)
  • 【数据结构与算法篇】手撕排序算法之插入排序与希尔排序

    ​👻内容专栏:《数据结构与算法篇》 🐨本文概括: 讲述排序的概念、直接插入排序、希尔排序、插入排序和希尔排序的区别。 🐼本文作者:花 碟 🐸发布时间:2023.6.13 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的

    2024年02月09日
    浏览(52)
  • 数据结构初阶之插入排序与希尔排序详解

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 一.前言 二.插入排序 2.1插入排序的思想 2.2代码实现 三.希

    2024年02月02日
    浏览(48)
  • 【数据结构】常见排序算法——常见排序介绍、插入排序、直接插入排序、希尔排序

      在计算机科学中,排序是将一组数据按照指定的顺序排列的过程。排序算法由于执行效率的不同可以分为多种不同的算法。   通常情况下,排序算法可以分为两类,即 内部排序和外部排序 。内部排序是指数据全部加载到内存中进行排序,适用于数据量较小的情况,而

    2024年02月08日
    浏览(63)
  • 【数据结构】 七大排序详解(壹)——直接插入排序、希尔排序、选择排序、堆排序

    排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而

    2024年02月09日
    浏览(67)
  • 直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序——“数据结构与算法”

    各位CSDN的uu们你们好呀,今天小雅兰的内容是数据结构与算法啦,是排序!!!下面,让我们进入七大排序的世界吧!!! 排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在

    2024年02月15日
    浏览(71)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包