[数据结构 -- 手撕排序第二篇] 一篇带你详细了解希尔排序

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

目录

1、常见排序算法

1.1 插入排序基本思想

2、希尔排序

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

2.1.1 预排序阶段

2.1.2 插入排序阶段

2.2 单趟希尔排序

2.2.1 思路分析

2.2.2 代码实现

3、希尔排序代码实现

4、希尔排序时间复杂度

5、希尔排序与插入排序效率对比

6、希尔排序特性总结


1、常见排序算法

1.1 插入排序基本思想

直接插入排序是一种简单的插入排序法,其基本思想是 :
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为
止,得到一个新的有序序列
实际中我们玩扑克牌时,就用了插入排序的思想

[数据结构 -- 手撕排序第二篇] 一篇带你详细了解希尔排序,排序算法,排序算法,算法,数据结构,c语言

2、希尔排序

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

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数gap,把待排序文件中所有记录分成多个组,所有距离相差为gap的记录分在同一组内,并对每一组内的记录进行排序。然后,取gap=gap/3+1重复上述分组和排序的工作。当到达gap=1时,所有记录在统一组内排好序。

我们画图来分析一下:我们这里是排升序

[数据结构 -- 手撕排序第二篇] 一篇带你详细了解希尔排序,排序算法,排序算法,算法,数据结构,c语言

由图我们其实可以看出来,当最后一次gap=1时,本质是插入排序,而希尔排序就是先预排序,最后再插入排序一次就实现了排序

我们将上面的图来分析一下:

2.1.1 预排序阶段

1、第一趟,当gap=5时,意思是每间隔5个数为一组,9与4,1与8,2与6,5与3,7与5分为一组,当后面的数字小于前面的数字我们就交换,这样我们就将这几组中小的数字排到了前面,大的数字就排到了后面;

2、第二趟,我们就让gap = gap/3+1(这里gap/3+1是为了最后能得到gap=1,当gap<3时,如果只是除以3,得到的就是0,这样就实现不了完全排序),gap=2,每间隔2个数为一组,4与2,5,8,5一组,1与3,9,6,7一组,比较大小,然后交换;

2.1.2 插入排序阶段

3、当调整gap=1时,本质就是插入排序了,这时经过了之前的预排序阶段,我们的数字已经接近有序了,但是不完全有序,此时上插入排序,效率提升会很大。

2.2 单趟希尔排序

2.2.1 思路分析

单趟的希尔排序其实就是将相隔为gap的数字分为一组,先进行排序。

画图分析:

[数据结构 -- 手撕排序第二篇] 一篇带你详细了解希尔排序,排序算法,排序算法,算法,数据结构,c语言

将单趟的每个间隔为gap的数字分为一组先进行排序。

2.2.2 代码实现

for (int i = 0; i < n - gap; i++)//多组一起排序(没有提升效率,只是少写一组循环)
{
    int end = i;
    int tmp = a[i + gap];
    while (end >= 0)
    {
        if (a[end] > tmp)
        {
            a[end + gap] = a[end];
            end -= gap;
        }
        else
        {
            break;
        }
    }
    a[end + gap] = tmp;
}

3、希尔排序代码实现

给单趟排序外面加一层循环,让gap不断缩小,直到为 1,就实现了希尔排序。

void ShellSort(int* a, int n)
{
	//1. 当 gap > 1 时先进性预排序
	//2. 当 gap == 1 时直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;// +1可以保证最后一次一定是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;
		}
	}
}

4、希尔排序时间复杂度

希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些书中给出的希尔排序的时间复杂度都不固定 。

以下是两本书对希尔排序时间复杂度的描述:

[数据结构 -- 手撕排序第二篇] 一篇带你详细了解希尔排序,排序算法,排序算法,算法,数据结构,c语言

我们这里的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照:O(n^1.25)到O(1.6*n^1.25)来算。

5、希尔排序与插入排序效率对比

我们分别开辟两个数组,都是100000大小,使用希尔排序与插入排序,对比所消耗的时间。

//时间对比
void TestOp()
{
	srand((unsigned int)time(NULL));
	const int n = 100000;
	int* a1 = (int*)malloc(sizeof(int) * n);
	int* a2 = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, n);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, n);
	int end2 = clock();


	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);

	free(a1);
	free(a2);
}

int main()
{
	TestOp();
	return 0;
}

[数据结构 -- 手撕排序第二篇] 一篇带你详细了解希尔排序,排序算法,排序算法,算法,数据结构,c语言

我们可以看出希尔排序要比插入排序的效率高出很多,当数据量越大的时候,希尔排序的更占优势。

但是,当数组本身就是有序的,希尔排序就比不过插入排序,因为希尔排序存在预排序,执行了就要花费时间。

6、希尔排序特性总结

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些书中给出的希尔排序的时间复杂度都不固定 。

4。稳定性:不稳定。文章来源地址https://www.toymoban.com/news/detail-543428.html

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

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

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

相关文章

  • 数据结构修炼第二篇:顺序表和链表

    第一章 时间复杂度和空间复杂度 第二章 顺序表,列表 第三章 栈和队列 第四章 二叉树 第五章 排序 作者:🎈乐言🎈 简介:🎈大一学生,目前在致力于c/c++/python,高数的学习,有问题尽管问我,关注后私聊! 持续更新专栏:《c进阶》,《数据结构修炼》 🚀 (优质好文持

    2024年02月02日
    浏览(111)
  • 【数据结构】手撕排序

    🔥 博客主页 : 小羊失眠啦. 🎥 系列专栏 : 《C语言》 《数据结构》 《Linux》 《Cpolar》 ❤️ 感谢大家点赞👍收藏⭐评论✍️ 排序 :所谓排序就是使一串记录,按照其中的某个或某些的大小, 递增或递减 的排列起来的操作。排序算法,就是如何使得记录按照要求

    2024年02月05日
    浏览(50)
  • 【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式

    目录 前言:  中缀表达式:  后缀表达式: 中缀表达式转后缀表达式: 后缀表达式计算结果: 总结:  计算机在计算四则运算的时候,由于括号以及运算优先级的存在,并不能够很好的处理所有的运算,为了处理这种情况,我们引入了后缀表达式来优化算法。         

    2024年02月13日
    浏览(53)
  • [数据结构 -- 手撕排序第三篇] 冒泡排序

    目录 1、常见的排序算法 1.1 交换排序基本思想 2、冒泡排序的实现 2.1 基本思想 2.2 单趟排序 2.2.1 单趟排序分析 2.2.2 单趟排序实现代码 3、冒泡排序完整代码实现 3.1 思路分析 3.2 代码实现 4、时间复杂度 5、优化算法 5.1 优化算法思路 5.2 优化算法代码实现 6、冒泡排序的特性总

    2024年02月13日
    浏览(44)
  • 【数据结构】手撕排序NO.1----排序初识

    目录  一. 前言 二. 排序的概念及运用         2.1 排序的概念         2.2 排序的运用         2.3 常见的排序算法 三. 冒泡and选择排序         3.1 冒泡排序         3.2 选择排序 四. 各大排序算法的复杂度和稳定性        从本期开始,我们的数据结构将迎来一个新的

    2024年02月16日
    浏览(54)
  • 【数据结构】手撕归并排序(含非递归)

    目录 一,归并排序(递归) 1,基本思想  2,思路实现 二,归并排序(非递归) 1,思路实现 2,归并排序的特性总结: 1,基本思想 归并排序 (MERGE-SORT) 是建立在 归并操作 上的一种 有效的排序算法 ,该算法是采用 分治法(Divide and Conquer) 的一个非常典型的应用; 将 已

    2024年02月08日
    浏览(46)
  • 【数据结构】手撕排序NO.2----直接插入排序与希尔排序

      目录 一. 导入 二. 直接插入排序         2.1 基本思想         2.2 过程分析         2.3 代码实现         2.4 复杂度/稳定性分析 三. 希尔排序(缩小增量排序)         3.1 基本思想         3.2 过程分析          3.3 代码实现          3.4 复杂度/稳定性分析  

    2024年02月14日
    浏览(41)
  • [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    目录 1、归并的思想 2、归并排序的思想 2.1 基本思想 2.2 图解分析 3、归并排序递归版本代码实现 3.1 代码解析 3.2 注意事项 3.2.1错误划分:[begin, mid-1],[mid, end] 3.2.2 正确划分:[begin, mid], [mid+1, end] 4、归并排序的测试 5、时间复杂度、空间复杂度分析 5.1 时间复杂度 5.2 空间复杂

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

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

    2024年02月09日
    浏览(48)
  • 数据结构与算法之手撕排序算法

    为什么要学习排序算法? 根据统计,早起大型机CPU资源的四分之一都花在了数据排序上面。排序算法作为最基础的算法,各种操作系统、编程语言都提供了内置的实现。既然排序实现随处可见,我们为什么还要自己动手实现呢?虽然经典算法要动手写写加深印象的道理都懂,

    2023年04月16日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包