首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【数据结构】排序(下)

【数据结构】排序(下)

作者头像
s-little-monster
发布于 2024-06-18 01:45:22
发布于 2024-06-18 01:45:22
11201
代码可运行
举报
运行总次数:1
代码可运行

二、常见排序的实现

8、快速排序的优化

当我们使用快速排序时,最坏的情况就是数组有序,此时的时间复杂度为O(N^2) 最好的情况就是key每次取中位数 所以我们为了避免最坏情况的发生,我们在快速排序的基础上衍生了一种优化的方法叫做三数取中 还有一种方法是随机选key,但随机选key的效果不如三数取中

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] < a[right])
			return right;
		else
			return left;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] > a[right])
			return right;
		else
			return left;
	}
}

将三个比较出中间的数字作为key然后换到left上,进行partsort 在每个partsort的最前边加上这条语句,就优化了这个快速排序的结构

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int PartSort(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	......
}

9、非递归快速排序

(1)基本思想

前边我们讲的快速排序是基于递归条件下实现的,但我们知道,递归会消耗栈上的空间,并且栈上的空间比较小,不能实现大量数据的快速排序,所以我们要将这个过程放在空间更大的堆上,也就是使用栈来实现 栈的作用就是存储区间,这个区间由两个整数组成,通过出入栈来模拟递归的过程

(2)代码实现

这里需要包含一下以前我们写过的栈的头文件

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	StackInit(&st);
	StackPush(&st,right);
	StackPush(&st, left);

	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
        //取出区间
        
		int keyi = PartSort1(a, left, right);
		//通过keyi将数据区间一分为二
		
		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
		//存入区间
	}
	StackDestroy(&st);
}
(3)时间复杂度

同递归方式的快速排序,为O(log₂N * N)

(4)空间复杂度

同递归方式的快速排序,为O(log₂N)

10、归并排序

(1)基本思想

将一个待排序的序列分为若干个子序列,每个子序列都是有序的,然后再将有序的序列合并为整体的有序序列

(2)代码实现
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left == right)
		return;
	
	//找到中间下标
	int midi = (left + right) / 2;
	
	//一分为二二分为四的分开
	_MergeSort(a, left, midi, tmp);
	_MergeSort(a, midi + 1, right, tmp);
	
	int begin1 = left, end1 = midi;
	int begin2 = midi + 1, end2 = right;
    
    //i用来记录容器数组中对应的下标
	int i = left;
	
	//将两个数组中按升序归并到容器数组中
	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 + left, tmp + left, sizeof(int) * (right - left + 1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}
(3)时间复杂度

归并排序分为两个过程 一是分解过程,这是一个类二叉树的过程,由中间下标分为两个区间,再分为四个区间,以此类推,此过程的时间复杂度是O(log₂N) 二是合并过程,合并过程中需要遍历整个数组,找到谁大谁小然后排序,这个过程的时间复杂度是O(N) 整个过程的时间复杂度就是O(N*log₂N)

(4)空间复杂度

该过程需要在堆上开辟n个空间,以及递归所需要的log₂n个在栈上的空间,由于对于n来说log₂n很小,所以它的空间复杂度为O(N)

11、非递归归并排序

(1)基本思想

与快速排序相同,递归方式的归并排序需要使用栈中空间,在处理大量数据时空间不够,所以我们可以用循环的方法减少栈的使用,这就是非递归的归并排序

(2)代码实现
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int gap = 1;
	while (gap < n)
	{
		int j = 0;//作为tmp的下标
		for (int i = 0; i < n; i += 2*gap)//每次跳过两组数据
		{
	    	//这里的间隔差gap,每次比较两组数据
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap * 2 - 1;
		
			//以下同上
			if (end1 >= n || begin2 >= n)
				break;
			if (end2 >= n)
				end2 = n - 1;
				
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[j++] = a[begin1++];
				else
					tmp[j++] = a[begin2++];
			}
			
			while (begin1 <= end1)
				tmp[j++] = a[begin1++];
			while (begin2 <= end2)
				tmp[j++] = a[begin2++];
				
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;//while结束后把间隔调两倍
	}
	free(tmp);
}
(3)时间复杂度

for循环每次gap*=2,时间复杂度为O(log₂N),for循环中遍历了一遍数组,时间复杂度为O(N) 总的时间复杂度为O(N * log₂N)

(4)空间复杂度

申请了堆上的n个空间,空间复杂度为O(N)

12、非比较排序

(1)基本思想

计数排序是一种非比较排序,实现过程中不需要任何的比较 第一步:统计相同元素出现的次数 第二步:根据统计的结果将序列回收到原来的序列当中 这个排序适用于数据比较集中的序列

(2)代码实现
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void CountSort(int* a, int n)
{
	int min, max;
	min = max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int range = max - min + 1;
	//找到这一组数据中最大和最小的数相减得出这组数据的范围
	int* countA = (int*)malloc(sizeof(int) * range);
	memset(countA, 0, sizeof(int)*range);
	//创建一个在堆上的数组作为计数数组,大小为这组数据的范围,将其中的元素全部重置为0
	for (int i = 0; i < n; i++)
		countA[a[i] - min]++;
	//将每个数字出现的次数记录
	int k = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)
			a[k++] = i + min;
	}
}//下标加上整个数组的最小值就是当前数据的大小,countA为0时退出循环,不为0就记录下来
(3)时间复杂度

找出最大最小值需要遍历一遍数组,记录数字走for循环中range 所以时间复杂度为O(N+range),当数据比较集中时,时间复杂度接近O(N) 到底是O(N)还是O(range)取决于它们俩哪个大

(4)空间复杂度

在堆上开辟了range个空间,空间复杂度为O(range),当数据比较集中时,空间复杂度接近O(1)

三、各个排序方法所用时间的比较

1、代码实现

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);


	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();//取随机值
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
		//赋值给所有数据
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
//clock是一个函数,用于记录当前时间点,在开始时记录一下,在结束后记录一下
//得出的时间差就是这个排序所用的时间
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	BubbleSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	SelectSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	HeapSort(a5, N);
	int end5 = clock();

	int begin6 = clock();
	QuickSort(a6, 0, N - 1);
	int end6 = clock();

	int begin7 = clock();
	MergeSort(a7, N);
	int end7 = clock();

	int begin8 = clock();
	CountSort(a8, N);
	int end8 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("BubbleSort:%d\n", end3 - begin3);
	printf("SelcetSort:%d\n", end4 - begin4);
	printf("HeapSort:%d\n", end5 - begin5);
	printf("QuickSort:%d\n", end6 - begin6);
	printf("MergeSort:%d\n", end7 - begin7);
	printf("CountSort:%d\n", end8 - begin8);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);
}

2、分析

当数据给到10W个时,我们可以明显看出各个排序的差距 最拉胯的就是冒泡排序,跟其他排序所用时间都不在一个量级上 然后就是直接插入以及选择插入 然后就是希尔排序、堆排序、快速排序、归并排序 因为随机数的生成是由时间戳实现的,两个随机数之间差的并不多,所以范围比较集中,这就使得计数排序超级快

四、各个排序的稳定性

1、基本概念

稳定性好就是一个序列中存在着两个即两个以上的相同数据,这两个数据在排序前后相对位置不变,反之就是不好 这里的前后相对位置不变不是指它们两个数据一直待在原来的位置,而是前边的数字a1在排列后还在后边的数字a2前边,而不是跑到它的后边了

2、各个排序的稳定性复杂度一览表

排序方法

平均情况

最好情况

最坏情况

辅助空间

稳定性

冒泡排序

O(N^2)

O(N)

O(N^2)

O(1)

稳定

简单选择排序

O(N^2)

O(N^2)

O(N^2)

O(1)

不稳定

直接插入排序

O(N^2)

O(N)

O(N^2)

O(1)

稳定

希尔排序

O(N ^log₂N)~O(N ^2)

O(N^1.3)

O(N^2)

O(1)

不稳定

堆排序

O(N^log₂N)

O(N^log₂N)

O(N^log₂N)

O(1)

不稳定

归并排序

O(N^log₂N)

O(N^log₂N)

O(N^log₂N)

O(N)

稳定

快速排序

O(N^log₂N)

O(N^log₂N)

O(N^2)

O(log₂N)~O(N)

不稳定

感谢观看

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-06-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
VBA实用小程序:核查并标记公式是否被正确复制
下面的代码将复制活动工作表,然后标记公式,使用阴影显示已复制哪些以及从何处复制。它从左到右、从上到下进行核查。
fanjy
2023/02/14
5390
VBA实用小程序:核查并标记公式是否被正确复制
VBA拆分工作簿示例
如下图1所示,列B中有一系列重复数据,想要将每个重复的数据所在的行放到一个新工作簿并以该数据作为工作簿名。例如,列B中为7890的所有行复制到一个新工作簿并命名为7890.xlsx。
fanjy
2024/06/19
2690
VBA拆分工作簿示例
ExcelVBA拆分_一簿一表_to_多簿一表
哆哆Excel
2023/09/09
3090
ExcelVBA拆分_一簿一表_to_多簿一表
ExcelVBA拆分之一簿一表_to_一簿多表使用演示
哆哆Excel
2023/09/09
3080
VBA: 将单元格区域作为邮件正文发送到指定邮箱
文章背景: 在工作中,有时需要将单元格区域的内容作为邮件正文发送到指定邮箱,如果希望邮件正文中的单元格区域带表格样式,则需要将其转换为html格式。
Exploring
2024/04/15
9390
VBA: 将单元格区域作为邮件正文发送到指定邮箱
VBA专题02:使用代码进行复制操作
在Excel工作表中,复制粘贴是最常用的操作之一。在已经输入的数据中,找到并复制想要的数据,然后粘贴到指定的地方,是再自然不过的操作了。或者从工作表的一个单元格区域复制到同一工作表中另外的单元格区域,或者从工作表的一个单元格区域复制到另一工作表中的单元格区域,甚至从工作表的一个单元格区域复制到不同工作簿中的工作表单元格区域。那么,如何使用VBA代码来实现复制粘贴操作呢?本文将介绍常用的一些代码。
fanjy
2019/07/19
7.4K0
ExcelVBA从工作簿中查询多个姓名并复制出整行数据
工作中用的代码 Sub ExcelVBA从工作簿中查询多个姓名并复制出整行数据() Dim outFile As String, inFile As String Dim outWb As Workbook, mysht As Worksheet, tempsht As Worksheet, t_arr(1 To 30) Dim SearchRange As Range Dim LastRow As Integer, arr, FindStr As String, i
哆哆Excel
2022/10/31
1.9K0
VBA实用小程序:将Excel中的内容输入到Word
将Excel数据输入到Word文档并不难,但这会破坏书签,如果你在对Word文档进行了大量修改后发现想要重新从Excel中输入数据,那可能会令人沮丧。我想要一个可以根据需要经常重复的将Excel数据输入到Word,这意味着在复制完成后要重新创建书签。
fanjy
2023/02/14
2.8K0
ExcelVBA拆分之一簿一表_to_一簿多表
哆哆Excel
2023/09/09
3070
ExcelVBA拆分之一簿一表_to_一簿多表
ExcelVBA筛选法按分类条件拆分一个工作表为多个工作簿
对上次的文章进行优化 ==========代码如下===== Sub 筛选拆分() Dim d As Object, sht As Worksheet, arr, brr, r, kr, i&, j&, k&, x& Dim Rng As Range, Rg As Range, tRow&, tCol& Dim wb As Object, mysht As Worksheet Set d = CreateObject("scripting.dictionary") 'se
哆哆Excel
2022/10/31
3.9K1
ExcelVBA条件查找多文件并由整行复制到模板再存为新工作簿
【解决问题】在工作中我常要做的事:在几个文件中,查找某人的数据,并复制出来,到一个新的文件中。
哆哆Excel
2022/10/31
1.2K0
使用VBA将工作簿中所有的数据转换成值
通常,工作簿中会包含很多工作表,而工作表中的数据有些是单纯的数值,而有些是公式的结果。如果我们想要将工作簿中所有的数据都转换为值,也就是说,公式转换为其结果值,如何快速实现呢?
fanjy
2022/11/16
1.6K0
VBA基础:复制格式、选取单元格及复制工作表的示例代码
fanjy
2024/05/25
7640
VBA基础:复制格式、选取单元格及复制工作表的示例代码
VBA: 获取共享工作簿的当前在线用户
在日常工作中,尽管 Microsoft 已不再推荐使用“共享工作簿(Shared Workbook)”功能,但工作中,由于协作方式的限制,旧版共享工作簿功能依然广泛存在。
Exploring
2025/05/24
740
VBA: 获取共享工作簿的当前在线用户
VBA代码:将多个文本文件合并到当前工作表
下面分享在vbaexpress.com中收集的几段代码,用于合并文本文件并将其放置在当前工作表中。
fanjy
2024/06/04
4440
VBA代码:将多个文本文件合并到当前工作表
EXCEL VBA语句集300
        定制模块行为 (1) Option Explicit ‘强制对模块内所有变量进行声明 Option Private Module ‘标记模块为私有,仅对同一工程中其它模块有用,在宏对话框中不显示  Option Compare Text ‘字符串不区分大小写  Option Base 1 ‘指定数组的第一个下标为1 (2) On Error Resume Next ‘忽略错误继续执行VBA代码,避免出现错误消息 (3) On Error GoTo ErrorHandler ‘当错误发生时跳转到过程中的某个位置 (4) On Error GoTo 0 ‘恢复正常的错误提示 (5) Application.DisplayAlerts=False ‘在程序执行过程中使出现的警告框不显示 (6) Application.ScreenUpdating=False ‘关闭屏幕刷新 Application.ScreenUpdating=True ‘打开屏幕刷新 (7) Application.Enable.CancelKey=xlDisabled ‘禁用Ctrl+Break中止宏运行的功能  工作簿 (8) Workbooks.Add() ‘创建一个新的工作簿 (9) Workbooks(“book1.xls”).Activate ‘激活名为book1的工作簿 (10) ThisWorkbook.Save ‘保存工作簿 (11) ThisWorkbook.close ‘关闭当前工作簿 (12) ActiveWorkbook.Sheets.Count ‘获取活动工作薄中工作表数 (13) ActiveWorkbook.name ‘返回活动工作薄的名称 (14) ThisWorkbook.Name ‘返回当前工作簿名称 ThisWorkbook.FullName ‘返回当前工作簿路径和名称 (15) ActiveWindow.EnableResize=False ‘禁止调整活动工作簿的大小 (16) Application.Window.Arrange xlArrangeStyleTiled ‘将工作簿以平铺方式排列 (17) ActiveWorkbook.WindowState=xlMaximized ‘将当前工作簿最大化  工作表 (18) ActiveSheet.UsedRange.Rows.Count ‘当前工作表中已使用的行数 (19) Rows.Count ‘获取工作表的行数(注:考虑向前兼容性) (20) Sheets(Sheet1).Name= “Sum” ‘将Sheet1命名为Sum (21) ThisWorkbook.Sheets.Add Before:=Worksheets(1) ‘添加一个新工作表在第一工作表前 (22) ActiveSheet.Move After:=ActiveWorkbook. _ Sheets(ActiveWorkbook.Sheets.Count) ‘将当前工作表移至工作表的最后 (23) Worksheets(Array(“sheet1”,”sheet2”)).Select ‘同时选择工作表1和工作表2 (24) Sheets(“sheet1”).Delete或 Sheets(1).Delete ‘删除工作表1 (25) ActiveWorkbook.Sheets(i).Name ‘获取工作表i的名称 (26) ActiveWindow.DisplayGridlines=Not ActiveWindow.DisplayGridlines ‘切换工作表中的网格线显示,这种方法也可以用在其它方面进行相互切换,即相当于开关按钮 (27) ActiveWindow.DisplayHeadings=Not ActiveWindow.DisplayHeadings ‘切换工作表中的行列边框显示 (28) ActiveSheet.UsedRange.FormatConditions.Delete ‘删除当前工作表中所有的条件格式 (29) Cells.Hyperlinks.Delete ‘取消当前工作表所有超链接 (30) ActiveSheet.PageSetup.Orientation=xlLandscape 或ActiveSheet.PageSetup.Orientation=2 ‘将页面设置更改为横向 (31) ActiveSheet.PageSetup.RightFooter=ActiveWorkbook.FullName ‘在页面设置的表尾中输入文件路径 ActiveSheet.PageSetup.Le
Tony老师
2020/03/05
2.8K0
VBA: 遍历文件抓取指定条件的数据
文章背景:要查看某次考试成绩不及格的所有学生名单;假定按年级建文件夹,每个文件夹内有各班的考试成绩表(见下图)。需要遍历所有表格,然后对每行的学生成绩进行判断。
Exploring
2022/08/10
1.7K0
VBA: 遍历文件抓取指定条件的数据
列出工作簿中的所有公式及其位置和值
下面的程序将在一个新工作表中列出当前工作簿中所有工作表中的公式,以及这些公式所有的工作表、单元格及值。
fanjy
2023/12/20
5860
列出工作簿中的所有公式及其位置和值
ExcelVBA汇总-多簿一表_to_一簿一表
哆哆Excel
2023/09/09
3290
ExcelVBA汇总-多簿一表_to_一簿一表
VBA汇总一个文件多工作表到一个表
VBA汇总一个文件多工作表到一个表 . 今天在工作中,同事传来一个excel文件中有很多个工作表,要我汇总,每个表的标题是一样的,虽然一个一个复制、粘贴是可以做到的,但时间很长,所以把以前学习一个代码,拿来用一下,代码找了很久才找到,想想还是把他放在这里好一点,以后查找方便 . 把多个工作表的内容汇总到一个“汇总”表中 Sub sheets_to_one() Dim mysht As Worksheet, rng As Range, sht As Worksheet Dim
哆哆Excel
2022/10/31
6520
相关推荐
VBA实用小程序:核查并标记公式是否被正确复制
更多 >
LV.1
这个人很懒,什么都没有留下~
目录
  • 二、常见排序的实现
    • 8、快速排序的优化
    • 9、非递归快速排序
      • (1)基本思想
      • (2)代码实现
      • (3)时间复杂度
      • (4)空间复杂度
    • 10、归并排序
      • (1)基本思想
      • (2)代码实现
      • (3)时间复杂度
      • (4)空间复杂度
    • 11、非递归归并排序
      • (1)基本思想
      • (2)代码实现
      • (3)时间复杂度
      • (4)空间复杂度
    • 12、非比较排序
      • (1)基本思想
      • (2)代码实现
      • (3)时间复杂度
      • (4)空间复杂度
  • 三、各个排序方法所用时间的比较
    • 1、代码实现
    • 2、分析
  • 四、各个排序的稳定性
    • 1、基本概念
    • 2、各个排序的稳定性复杂度一览表
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档