【算法】关于排序你应该知道的一切(上)

这篇具有很好参考价值的文章主要介绍了【算法】关于排序你应该知道的一切(上)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构

和光同尘_我的个人主页
单程孤舟,出云入霞,如歌如吟。 --门孔

🕯️前言

国庆快乐!!本来想把排序都做到一起的,才写了一半就八千多字了,那就分开发吧,一如既往的详细哦⌨️

1. 排序的概念及其运用

1.1. 排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

内部排序:数据元素全部放在内存中的排序。

外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

1.2. 排序的应用

数据库查询:在数据库中,经常需要根据某个字段对数据进行排序,以便更快地进行查询和检索。排序算法可以用于对数据库中的数据进行排序,从而提高查询效率。

搜索算法:许多搜索算法的实现需要对数据进行排序。例如,在二分查找算法中,要求待搜索的数据必须是有序的。因此,使用排序算法对数据进行排序,可以提高搜索算法的效率。

负载均衡:在分布式系统中,负载均衡是一种优化策略,通过将工作负载均匀地分配给各个节点,以提高系统的性能和吞量。排序算法可以用于对请求或任务进行排序,以便将工作负载均匀地分布给各个节点。

数据压缩:在数据压缩算法中,排序算法可以用于对数据进行预处理,以便更好地利用压缩算法的特性。例如,在哈夫曼编码中,可以根据字符频率对字符进行排序,以便构建最优的编码树。

排序和统计:在统计分析中,需要对数据进行排序,以便进行数据的聚合、分组和分析。排序算法可以用于对数据进行排序,从而更方便地进行统计分析。

任务调度:在任务调度算法中,排序算法可以用于对任务进行排序,以便根据任务的优先级、截止时间或其他标准进行合理的任务调度和分配。

1.3. 常见排序算法

【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构

2. 常见排序算法实现

2.1. 直接插入排序

2.1.1. 基本思想

把数据按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

*举个栗子,摸扑克牌时按大小一张一张往里面插入,就是这个意思
【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构

  • 大致流程:
    1. 从一个有序数组开始(一个数据也算有序)
    2. 将待插入的数据与数组比较,找到合适的位置,插入,形成一个新的有序数组
    3. 重复上面的步骤,即从只有第一个元素的有序数组开始,将后面所有元素逐个插入到数组

2.1.2. 代码实现

  • 关于排序代码的实现,建议可以先写出一个单趟排序(单趟即对所有元素处理一遍)
void InsertSort(int* a, int n)
{
	//假设end前的数据有序,end为有序数组最后一位
	int end = x;

	//保存要插入数据的值
	int tmp = a[x + 1];

	while(end >= 0)
	{
		//大于tmp则往后挪动
		if (a[end] > tmp)
			a[end + 1] = a[end];
		
		//找到了合适位置break
		else
			break;
			
		end--;
	}
	//end指向的值是一个<=tmp的值,所以令end+1指向的值为tmp
	a[end + 1] = tmp;	
}
  • 而后我们就可以轻松写出整个排序了
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{	
		//通过i从第一个元素开始,保证了end为有序数组的最后一位
		int end = i;
		int tmp = a[i + 1];
		while(end >= 0)
		{
			if (a[end] > tmp)
				a[end + 1] = a[end];
			else
				break;
			end--;
		}
		a[end + 1] = tmp;	
	}
}

2.1.3. 特性

空间复杂度:O(1)

时间复杂度:
最坏情况(数组为降序序):时间复杂度O(N^2)
最好情况(数组为升序):时间复杂度O(N)
平均时间复杂度O(N^2)

稳定性:稳定

  • 由此可以看出:元素集合越接近有序,直接插入排序算法的时间效率越高

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

2.2.1. 基本思想

  • 元素集合越接近有序,直接插入排序的时间效率越高,通过预处理使数组先接近有序,在进行插入排序。希尔排序是对直接插入排序的优化。

先选定一个整数gap,把待排序文件中所有记录分成gap个组,所有距离gap为的记录分在同一组内,并对每一组内的记录进行排序。然后,取gap = gap / 3 + 1(或gap = gap / 2),重复上述分组和排序的工作。当到达gap=1时(即直接插入排序),所有记录在统一组内排好序。

【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构
【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构

2.2.2. 代码实现

同样,我们先写一个单趟排序,可以在插入排序的基础上直接修改
我们把所有的1替换为gap

void ShellSort(int* a, int n)
{
	int gap = n / 3 + 1;
	for (int i = 0; i < n - gap; i += gap)
	{
		int end = i;
		int tmp = a[i + gap];
		while (end >= 0)
		{
			if (a[end] > tmp)
				a[end + gap] = a[end];
			else
				break;
			end -= gap;
		}
		a[end + gap] = tmp;
	}
}
  • 以这组数据为例,由于我们这样设计循环体for (int i = 0; i < n - gap; i += gap),上面的代码实际上只会对图中的第一组数据(①)进行排序
    【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构
  • 而我们要完成对所有数据处理一遍,普遍容易想到的是再加一层循环
for(int j = 0; j < gap; j++) 
{
	int gap = n / 3 + 1;
	for (int i = j; i < n - gap; i += gap)
  • 在上面的代码中,通过第一个循环体,我们实现了依次对①、②、③、④组数据的排序,但这样的代码循环太多了,可以简化一下。

由于每组数据是独立的,其他组数据的交换不影响本组数据,我们可以拆分各组数据交换的过程,如下图,由①、②、③、④组数据依次交换,变为交换①.1、②.1、③、④、①.2、②.2 ,同样完成了对四组数据的分别排序
【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构

  • 这样的代码实现起来,只需要把for (int i = j; i < n - gap; i += gap)中的i += gap换成i++就可以了
    整体如下
void ShellSort(int* a, int n)
{
	int gap = n / 3 + 1;
	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];
			else
				break;
			end -= gap;
		}
		a[end + gap] = tmp;
	}
}
  • 这样我们就完成了单趟排序,接下来只要控制gap变量,让它减小,直到gap==1(即直接插入排序),整个排序就完成了
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		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];
				else
					break;
				end -= gap;
			}
			a[end + gap] = tmp;
		}
	}
}

2.2.3.特性总结

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

空间复杂度:O(1)
时间复杂度:
希尔排序的时间复杂度计算相当麻烦,要用到专业的数学知识,官方复杂度为O(N^1.3),比O(N*logN)差一点。

gap较大时,比如gap == n / 3:数组分为n / 3组,每组3个数据,每组比较3次,合计(n / 3) * 3 = n次。

gap很小,比如gap = = 1:数组接近有序,直接插入,合计n次。

gap取中间的值,如n / 9:每组比较1+2+…+8=36次,合计36 * (n / 9) == 4n次。

里面的比较次数是逐渐变化的,两端比较次数少,越往中间比较次数越多,大致有这样的关系
【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构

2.3. 选择排序

2.3.1. 基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。

【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构

2.3.2. 代码实现

稍微加点难度,我们同时获得最大和最小数据,分别放在序列的首尾
直接开写!

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//用mini保存最小数据的位置,maxi保存最大数据的位置
		int mini = begin, maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			//碰到更小、更大的及时更新mini和maxi
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > a[maxi])
				maxi = i;
		}
		//将最小值放在其实位置,最大值放在末尾位置
		Swap(&a[begin], &a[mini]);
		Swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}
  • 这样的代码已经实现了我们的逻辑思想,可还有一点小问题

如果maxi==begin,就会发现,最小的min到了最后,最大的max位置却没有变
【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构
对于这样的情况我们稍加判断,在minibegin指向的数据交换后,如果maxi==begin,那么此时maxi指向的数据已经被begin交换到mini的位置了,就让maxi==mini

最终代码:

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > a[maxi])
				maxi = i;
		}
		Swap(&a[begin], &a[mini]);
		if (maxi == begin)
			maxi = mini;
		Swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}

2.3.3. 特性

时间复杂度:O(N^2)
空间复杂度:O(1)

2.4. 堆排序

这个前面讲过了哦,那我就开始CV了😂(主要再次展示下我当时呕心沥血画的图😎)

2.4.1. 基本思想

升序:建大堆 (降序:建小堆)
交换首尾,将根(最大的数)放在数组最后,并且不再调整这个数据
再把新的根向下调整,建大堆找到下一个最大的数,重复
堆排序也是一种选择排序

  • 堆排序流程(升序为例)
    【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构

2.4.2. 代码实现

void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
			child = child + 1;

		if (a[parent] < a[child])
			Swap(&a[parent], &a[child]);
		parent = child;
		child = parent * 2 + 1;
	}
}

void HeapSort(int* a, int n)
{
	for (int i = ((n - 1) - 1) / 2; i >= 0; i--)
		AdjustDwon(a, n, i);
	
	int end = n;
	while(end--)
	{
		//交换首尾,将根(最大的数)放在最后
		Swap(&a[0], &a[end]);

		//把新的根向下调整,找到下一个最大的数
		AdjustDwon(a, end, 0);
	}
}

2.4.3. 特性

时间复杂度:O(N*logN)
空间复杂度:O(1)


🗝️总结

  • 这几个排序还是比较简单的,自己一定多敲几遍熟悉代码哦😎,下一章我们讲快速排序和归并排序,xdm做好准备
本节完~~,如果你在实现过程中遇到任何问题,欢迎在评论区指出或者私信我!💕

新人博主创作不易,如果有收获可否👍点赞✍评论⭐收藏一下?O(∩_∩)O

【算法】关于排序你应该知道的一切(上),算法,c语言,数据结构文章来源地址https://www.toymoban.com/news/detail-734881.html

THANKS FOR WATCHING

到了这里,关于【算法】关于排序你应该知道的一切(上)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 关于ElasticSearch,你应该知道的

    一、集群规划优化实践 1、基于目标数据量规划集群 在业务初期,经常被问到的问题,要几个节点的集群,内存、CPU要多大,要不要SSD? 最主要的考虑点是:你的目标存储数据量是多大?可以针对目标数据量反推节点多少。 2、要留出容量Buffer 注意:Elasticsearch有三个警戒水

    2024年01月23日
    浏览(49)
  • Elasticsearch:关于在 Python 中使用 Elasticsearch 你需要知道的一切 - 8.x

    在本文中,我们将讨论如何在 Python 中使用 Elasticsearch。 如果你还不了解 Elasticsearch,可以阅读这篇文章 “Elasticsearch 简介” 进行快速介绍。在我之前的文章 “Elasticsearch:使用最新的 Python client 8.0 来创建索引并搜索”,我也有所介绍如何使用 Python 客户端来连接 Elasticsearch

    2024年02月02日
    浏览(30)
  • Diffusion Transformer Family:关于Sora和Stable Diffusion 3你需要知道的一切

    转自知乎:叫我Alonzo就好了 近期,OpenAI和Stability两大AI巨头公司在同期分别发布了它们的新作品——Sora和Stable Diffusion 3。神奇的是,这两家公司的研究团队不约而同地采用了Diffusion Transformer这一架构。Diffusion Transformer这个词倒是并不陌生,回想在DiT[3]刚挂出arXiv的时候,当时

    2024年03月18日
    浏览(53)
  • 【C++】关于多线程,你应该知道这些

    thread类的简单介绍 在 C++11 之前,涉及到多线程问题,都是和平台相关的,比如 Windows 和 Linux 下各有自己的接口,这使得代码的可移植性比较差。C++11 中最重要的特性就是对线程进行支持了,使得 C++ 在并行编程时不需要依赖第三方库,而且在原子操作中还引入了原子类的概

    2023年04月15日
    浏览(50)
  • 数据结构——排序算法(C语言)

    本篇将详细讲一下以下排序算法: 直接插入排序 希尔排序 选择排序 快速排序 归并排序 计数排序 排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某写的大小,按照递增或递减0排列起来的操作。 稳定性的概念 假定在待排序的记录序列中,存在多个

    2024年02月08日
    浏览(66)
  • 数据结构与算法——排序(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年04月09日
    浏览(59)
  • 内部排序算法比较-数据结构C语言课设

    名称: 内部排序算法比较 内容: 在教科书中,各种内部排序算法的时间复杂的分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各种算法的比较次数和移动次数,以取得直观感受。 任务: (1)对以下7中常会用的内部排序算法进行比较

    2024年02月12日
    浏览(55)
  • 【算法】--- 几分钟了解直接选择排序(排序中最简单的排序)+快排(解决一切的优质算法)(中)

    👧个人主页:@小沈熬夜秃头中୧⍤⃝❅ 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:算法 🔑本章内容:选择排序中的 直接选择排序 和交换排序中的 快速排序 送给各位💌:你被黑暗敲打恰恰说明你是光明本身 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:

    2024年02月08日
    浏览(45)
  • 每个程序员都应该知道的8大算法

    在编程开发中,算法是用于解决特定问题或完成特定任务的一组指令或过程。算法可以用任何编程语言表示,可以像一系列基本操作一样简单,也可以像涉及不同数据结构和逻辑的多步骤过程一样复杂。 算法的主要目标是接收输入、处理它并提供预期的输出。算法可以根据时

    2023年04月11日
    浏览(47)
  • 第11章:C语言数据结构与算法初阶之排序

    排序是一种非常重要的算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,

    2024年02月12日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包