【数据结构】一文了解七大排序算法

文章目录

  • 前言
  • 一.直接插入排序
    • 插入排序思想
    • 插入排序代码实现
    • 插入排序总结
  • 二.希尔排序
    • 希尔排序思想
    • 希尔排序代码实现
    • 希尔排序总结
  • 三.选择排序
    • 选择排序思想
    • 选择排序代码实现
    • 选择排序总结
  • 四.堆排序
    • 堆排序思想
    • 堆排序代码实现
    • 堆排序总结
  • 五、冒泡排序
    • 冒泡排序思想
    • 冒泡排序代码实现
    • 冒泡排序总结
  • 六、快速排序
    • 快速排序思想
    • 快速排序代码实现
    • 快速排序总结
  • 七.归并排序
    • 归并排序思想
    • 归并排序代码实现
    • 归并排序总结
  • 总结


在这里插入图片描述

前言

所谓排序算法,即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则,体现出一定的规律,因此,经处理后的数据便于筛选和计算,大大提高了计算效率。对于排序,我们首先要求其具有一定的稳定性,即当两个相同的元素同时出现于某个序列之中,则经过一定的排序算法之后,两者在排序前后的相对位置不发生变化。换言之,即便是两个完全相同的元素,它们在排序过程中也是各有区别的。今天,我们介绍一下常见的排序算法。
在这里插入图片描述


一.直接插入排序

在这里插入图片描述

插入排序思想

插入排序算法是基于某序列已经有序排列的情况下,通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行,即要插入序列中的元素最先和有序序列中最大的元素比较,若其大于该最大元素,则可直接插入最大元素的后面即可,否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是,每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中,寻找最适当的位置,直至全部记录插入完毕。执行过程中,若遇到和插入元素相等的位置,则将要插人的元素放在该相等元素的后面,因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。

插入排序代码实现

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;
	}
}

插入排序总结

直接插入排序的特性总结:

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

二.希尔排序

在这里插入图片描述

希尔排序思想

希尔排序的思想实际上是将数列一次又一次的预排序,让数组趋近于有序,之后在进行插入排序得到答案。预排序就是先将数组中的数进行分组,将相隔gap距离的树分为一组,在一组中进行插入排序使之有序,再将gap逐渐缩小,最后gap等于1时,就是插入排序。通过分组的方法可以让后面的数更快的来到前面,让前面的数更快的来到后面。但是gap越大,越不接近有序,gap太小效率提高就不明显,所以经过前人的多次实验得到,当gap处于gap=gap/3+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[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

}

希尔排序总结

希尔排序的特性总结:

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

三.选择排序

在这里插入图片描述

选择排序思想

选择排序的思想比较简单,首先我们需要遍历一遍数组,找到最小的值,再将最先的值与第一个值交换,这样就排好了第一个数。以此类推,遍历后面的数组,再找最小的数,与前面交换,最后有序。我们也可以升级一下,遍历一次数组,找到最大最小的两个数,最小的放前面,最大的放后面。但是要注意当你交换完最小的数后,最大的那个数可能位置会变化,要单独讨论。

选择排序代码实现

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

选择排序总结

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

四.堆排序

在这里插入图片描述

堆排序思想

堆排序首先就是建堆,我们通过从倒数第二层开始向下调整建堆。如果排升序就建大堆,排降序建小堆。以升序为例,我们通过建堆在根节点得到最大的数,再将最大的数与最后的数交换位置,最大的数就排好了,再通过建堆找第二大的数,最后有序。

堆排序代码实现

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child+1<n && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		end--;
		AdjustDown(a, end+1, 0);
	}

}

堆排序总结

堆排序的特性总结:

  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

五、冒泡排序

在这里插入图片描述

冒泡排序思想

冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较,根据比较结果和算法规则对该二元素的位置进行交换,这样逐个依次进行比较和交换,就能达到排序目的。冒泡排序的基本思想是,首先将第1个和第2个记录的关键字比较大小,如果是逆序的,就将这两个记录进行交换,再对第2个和第3个记录的关键字进行比较,依次类推,重复进行上述计算,直至完成第(n一1)个和第n个记录的关键字之间的比较,此后,再按照上述过程进行第2次、第3次排序,直至整个序列有序为止。排序过程中要特别注意的是,当相邻两个元素大小一致时,这一步操作就不需要交换位置,因此也说明冒泡排序是一种严格的稳定排序算法,它不改变序列中相同元素之间的相对位置关系。

冒泡排序代码实现

void BubbleSort(int* a, int n)
{
	int j = 0, i = 0;
	for (j = 0; j < n ; j++)
	{
		for (i = 0; i < n - j - 1; i++)
		{
			if (a[i] > a[i + 1])
			{
				int tmp = a[i];
				a[i] = a[i + 1];
				a[i + 1] = tmp;
			}
		}
	}
}

冒泡排序总结

冒泡排序的特性总结:

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

六、快速排序

在这里插入图片描述

快速排序思想

快速排序采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。

快速排序算法通过多次比较和交换来实现排序,其排序流程如下:
1、首先设定一个分界值,通过该分界值将数组分成左右两部分。
2、将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
3、然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
4、重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

快速排序代码实现

void QiuckSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = left;
	int begin = left, end = right;
	while (end > begin)
	{
		while(end > begin && a[end] >= a[keyi])
		{
			end--;
		}
		while (end > begin && a[begin] <= a[keyi])
		{
			begin++;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[keyi]);
	QiuckSort(a, left, begin - 1);
	QiuckSort(a, begin + 1, right);
}

快速排序总结

  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(logN)
  4. 稳定性:不稳定

七.归并排序

在这里插入图片描述

归并排序思想

归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

归并排序代码实现

void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid + 1, end);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a+begin, tmp+begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		return;
	}
	_MergeSort(a, tmp, 0, n - 1);
	free(tmp);
	tmp == NULL;
}

归并排序总结

归并排序的特性总结:

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

总结

以上就是今天要讲的内容,本文仅仅简单介绍了几种常见的排序算法,实际上还有计数排序,桶排序等许多排序算法。如果喜欢这篇文章,期待你的一键三连。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/793544.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

深化信创存储 ,XEDP 与 飞腾腾云 S5000C 完成兼容性认证

近日&#xff0c;XSKY星辰天合的统一数据平台 XEDP 与飞腾信息技术有限公司的高性能服务器 CPU 飞腾腾云 S5000C 完成兼容性互认证。 经过严格的测试与评估&#xff0c;双方产品在技术上兼容良好&#xff0c;运行稳定且性能优异&#xff0c;融合双方优势构筑的软件定义存储系统…

SpringBoot实战:轻松实现接口数据脱敏

一、接口数据脱敏概述 1.1 接口数据脱敏的定义 接口数据脱敏是Web应用程序中一种保护敏感信息不被泄露的关键措施。在API接口向客户端返回数据时&#xff0c;系统会对包含敏感信息&#xff08;如个人身份信息、财务数据等&#xff09;的字段进行特殊处理。这种处理通过应用特…

Go-知识测试-模糊测试

Go-知识测试-模糊测试 1. 定义2. 例子3. 数据结构4. tesing.F.Add5. 模糊测试的执行6. testing.InternalFuzzTarget7. testing.runFuzzing8. testing.fRunner9. FuzzXyz10. RunFuzzWorker11. CoordinateFuzzing12. 总结 建议先看&#xff1a;https://blog.csdn.net/a1879272183…

智能家居开发新进展:乐鑫 ESP-ZeroCode 与亚马逊 ACK for Matter 实现集成

日前&#xff0c;乐鑫 ESP-ZeroCode 与亚马逊 Alexa Connect Kit (ACK) for Matter 实现了集成。这对智能家居设备制造商来说是一项重大进展。开发人员无需编写固件或开发移动应用程序&#xff0c;即可轻松设计符合 Matter 标准的产品。不仅如此&#xff0c;开发者还可以在短短…

Python(四)---序列

文章目录 前言1.列表1.1.列表简介1.2.列表的创建1.2.1.基本方式[]1.2.2.list()方法1.2.3.range()创建整数列表1.2.4.推导式生成列表 1.3. 列表各种函数的使用1.3.1.增加元素1.3.2.删除元素1.3.3.元素的访问和计数1.3.4.切片1.3.5.列表的排序 1.4.二维列表 2.元组2.1.元组的简介…

内网安全:域内信息探测

1.域内基本信息收集 2.NET命令详解 3.内网主要使用的域收集方法 4.查找域控制器的方法 5.查询域内用户的基本信息 6.定位域管 7.powershell命令和定位敏感信息 1.域内基本信息收集&#xff1a; 四种情况&#xff1a; 1.本地用户&#xff1a;user 2.本地管理员用户&#x…

短链接day4

短链接管理 创建短链接数据库表 URI、URL和URN区别 : URI 指的是一个资源 &#xff1b;URL 用地址定位一个资源&#xff1b; URN 用名称定位一个资源。 举个例子&#xff1a; 去寻找一个具体的人&#xff08;URI&#xff09;&#xff1b;如果用地址&#xff1a;XX省XX市XX区…

使用 Google 的 Generative AI 服务时,请求没有包含足够的认证范围(scopes)

题意&#xff1a; Google generativeai 403 Request had insufficient authentication scopes. [reason: "ACCESS_TOKEN_SCOPE_INSUFFICIENT" 问题背景&#xff1a; I have tried the simple POC for generativeai on its own to do generate_content and it works…

【初阶数据结构】2.顺序表

文章目录 1.线性表2.顺序表2.1 概念与结构2.2 分类2.2.1 静态顺序表2.2.2 动态顺序表 2.3 动态顺序表的实现2.4 顺序表算法题2.4.1 移除元素2.4.2 删除有序数组中的重复项2.4.3 合并两个有序数组 2.5 顺序表问题与思考 1.线性表 线性表&#xff08;linear list&#xff09;是n…

JavaFx+MySql学生管理系统

前言: 上个月学习了javafx和mysql数据库,于是写了一个学生管理系统,因为上个月在复习并且有一些事情,比较忙,所以没有更新博客了,这个项目页面虽然看着有点简陋了,但是大致内容还是比较简单的,于是现在跟大家分享一下我的学生管理系统,希望对这方面有兴趣的同学提供一些帮助 &a…

19185 01背包问题

解决这个问题的关键是使用动态规划的方法。我们可以创建一个二维数组dp[i][j]&#xff0c;其中i表示考虑前i件物品&#xff0c;j表示背包的容量。dp[i][j]的值表示在考虑前i件物品&#xff0c;且背包容量为j时能获得的最大价值。 ### 算法步骤 1. 初始化一个二维数组dp&#x…

Qt常用基础控件总结—容器部件(QGroupBox类)

五、容器部件 按钮框控件QDialogButtonBox 类(很少用) 按钮组控件QButtonGroup 类(很少用) 组框控件QGroupBox 类 QGroupBox 类介绍 QGroupBox(组框),直接继承自 QWidget 类,因此使用该类创建的对象,可作为窗口使用,组框在外观上是可见的。 QGroupBox 类(组框),…

数据平滑处理(部分)

一、 移动平均&#xff08;Moving Average&#xff09; 是一种最简单的数据平滑方法&#xff0c;用于平滑时间序列数据。它通过计算一定窗口内数据点的平均值来减少噪音&#xff0c;同时保留数据的趋势。移动平均包括简单移动平均&#xff08;SMA&#xff09;或指数加权移动平均…

【爬虫】爬虫基础

目录 一、Http响应与请求1、Http请求2、Http响应3、状态码 二、Requests库1、发起GET请求2、发起POST请求3、处理请求头 三、BeautifulSoup库1、解析HTML文档2、查找和提取数据Ⅰ、查找单个元素Ⅱ、查找所有元素Ⅲ、使用CSS选择器Ⅳ、获取元素属性 四、爬取豆瓣电影榜 一、Http…

YOLOv10训练自己的数据集(交通标志检测)

YOLOv10训练自己的数据集&#xff08;交通标志检测&#xff09; 前言相关介绍前提条件实验环境安装环境项目地址LinuxWindows 使用YOLOv10训练自己的数据集进行交通标志检测准备数据进行训练进行预测进行验证 参考文献 前言 由于本人水平有限&#xff0c;难免出现错漏&#xff…

【Linux】日志

日志是记录软件运行过程中发生的事件的一种手段&#xff0c;通常包含以下内容&#xff1a; 时间戳&#xff1a;记录日志条目创建的确切时间。这对于追踪事件发生的时间顺序至关重要。日志级别&#xff1a;表示日志信息的严重性或重要性&#xff0c;常见的级别包括 DEBUG、INFO…

RisingWave 用例:流式 ETL、实时分析、事件驱动应用

RisingWave 非常适合以下类别的用例。 流式 ETL实时分析事件驱动应用 流式 ETL 是实时分析和事件驱动应用的基础。实时分析通过引入数据看板&#xff0c;扩展了流式 ETL&#xff0c;而事件驱动应用则在实时分析的基础上增加了逻辑&#xff0c;以评估条件是否触发后续行动。 …

【测开能力提升-fastapi框架】fastapi模版引擎简单使用

1.6 通过模版引擎返回HTM页面 import uvicorn from fastapi import FastAPI, Request from fastapi.templating import Jinja2Templatesapp FastAPI()# 初始化模版引擎存放位置 templates Jinja2Templates(directory"templates")app.get("/") async def…

2024年西安铁一中集训DAY1---- 杂题选讲

文章目录 牛客练习赛125 E 联谊活动&#xff08;枚举&#xff0c;分讨&#xff09;牛客练习赛125 F 玻璃弹珠&#xff08;类莫队&#xff0c;离线询问&#xff0c;数据结构&#xff09;2024ccpc长春邀请赛 D Parallel Lines&#xff08;随机化&#xff09;2024ccpc长春邀请赛 E…

分布式应用系统设计:即时消息系统

即时消息(IM)系统&#xff0c;涉及&#xff1a;站内消息系统 组件如下&#xff1b; 客户端&#xff1a; WEB页面&#xff0c;IM桌面客户端。通过WebSocket 跟ChatService后端服务连接 Chat Service&#xff1a; 提供WebSocket接口&#xff0c;并保持跟“客户端”状态的维护。…