排序(一)插入排序,希尔排序,选择排序,堆排序,冒泡排序

目录

一.排序

1.插入排序

2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序

二.整体代码

1.Sort.h

2.Sort.c

3.test.c

一.排序

1.插入排序

插入排序基本思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列

实现过程单趟排序:将插入值与前一个数进行比较,如果大就直接插入到后面,如果小,将前一个数后移,继续与之前的比较,小的话插入空的位置,否则继续向前比较

        我们可以将每一个排序分为单趟和整体排序,了解单趟排序,对于整体排序,我们可以将它看作将数据一个一个的向里面插入

void InsertSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; ++i)
	{
		//单趟排序,[0,end]有序,将end + 1向其中插入
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		//插入的值比数组内所有值都小
		a[end + 1] = tmp;
	}
}

插入排序特性总结:

1.时间复杂度:O(N^2),顺序时最好,逆序时最坏

2.空间复杂度:O(1)

3.稳定性:稳定

4.当排序的数组越接近有序,算法的时间效率越高

2.希尔排序

我们将希尔排序分为预排序(使数组接近有序),然后直接插入排序

预排序:把间距为gap的值分为一组,进行插入排序

以gap为3为例的图

        当gap的值越大时,前面大的值可以更快的到后面,后面小的值可以更快的到前面,但是gap越大,数组内数据越不接近有序,而当gap为1的,就相当于插入排序

// 希尔排序
void ShellSort(int* a, int n)
{
	//gap>1相当于预排序,让数组接近有序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//+1保证了gap最后一次一定为1
		//gap==1相当于直接插入排序
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

希尔排序特性总结:

1.希尔排序是对插入排序的优化

2.当gap>1时为预排序,是为了让数组更接近有序,gap==1时数组已经基本有序,插入时就会较快.对于整个过程可以起到优化

3.稳定性:不稳定

4.gap的时间复杂度不好计算,因为gap的值不同

        在下图中我们可以看到对于一组数据插入排序和希尔排序的处理时间

我们可以看到希尔排序的处理速度相比于插入排序提升很大

3.选择排序

        选择排序:我们在begin和end的区间内寻找到最小值和最大值的下标,将最小值和最大值找到分别置于首和尾后,++begin,--end,缩小区间,继续寻找,直到搜索完整个区间

选择排序特性总结:

1.直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2.时间复杂度：O(N^2)

3.空间复杂度：O(1)

4.稳定性：不稳定

我们可以看到选择排序的处理效率与直接插入排序差不多

4.堆排序

        堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆

堆排序在前面已经讲解过,在此不多解释

//向下调整
//小堆向下调整前提:左右子树都为小堆
//大堆向下调整前提:左右子树都为大堆
void AdjustDown(int* a, int n, int root)
{
	int parent = root;//将根节点位置给父节点
	int child = 2 * parent + 1;//子节点下标为2*parent+1

	while (child < n)//保证下标不越界
	{
		//找出左右孩子小的那个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		//若孩子的值大于父亲则交换,并将孩子下标给父亲,重新计算孩子下标
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		//如果孩子大,则说明为小堆,不需要向下调整
		else
		{
			break;
		}
	}
}

//堆排序
//1.升序建大堆
//2.降序建小堆
void HeapSort(int* a, int n)
{
	//建堆
	//假设树有N个节点,树高度:logN.时间复杂度:O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);//向下调整
	}

	int end = n - 1;//最后一个叶的下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]);

		AdjustDown(a, end, 0);
		--end;
	}
}

堆排序特性总结:

1. 堆排序使用堆来选数，效率就高了很多

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

5.冒泡排序

        冒泡排序:将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动,前后比较,大的就交换

// 冒泡排序
void BubbleSort(int* a, int n)
{
	assert(a);
	int end = n;
	while (end > 0)
	{
		int exchange = 0;
		for (int i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}

		//如果一趟冒泡中没有发生交换,则说明已经有序,不需要冒泡
		if (exchange == 0)
		{
			break;
		}
	}
}

冒泡排序特性总结:

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

二.整体代码

1.Sort.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>

void PrintArray(int* a, int n);
void Swap(int* p1, int* p2);
void AdjustDown(int* a, int n, int root);
// 插入排序
void InsertSort(int* a, int n);

// 希尔排序
void ShellSort(int* a, int n);

// 选择排序
void SelectSort(int* a, int n);

// 堆排序
void AdjustDown(int* a, int n, int root);
void HeapSort(int* a, int n);

// 冒泡排序
void BubbleSort(int* a, int n);

2.Sort.c

#include "Sort.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

// 插入排序
// 时间复杂度O(N^2),顺序有序时最好,逆序时最坏
//空间复杂度O(1)
void InsertSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; ++i)
	{
		//单趟排序,[0,end]有序,将end + 1向其中插入
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		//插入的值比数组内所有值都小
		a[end + 1] = tmp;
	}
}

// 希尔排序
void ShellSort(int* a, int n)
{
	//gap>1相当于预排序,让数组接近有序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//+1保证了gap最后一次一定为1
		//gap==1相当于直接插入排序
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// 选择排序
void SelectSort(int* a, int n)
{
	assert(a);

	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//在[bagin,end]之间找出最小数和最大数的下标
		int mini, maxi;
		mini = maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}

			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		//如果maxi和begin位置重叠,maxi需要修正
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);

		++begin;
		--end;
	}
}


//向下调整
//小堆向下调整前提:左右子树都为小堆
//大堆向下调整前提:左右子树都为大堆
void AdjustDown(int* a, int n, int root)
{
	int parent = root;//将根节点位置给父节点
	int child = 2 * parent + 1;//子节点下标为2*parent+1

	while (child < n)//保证下标不越界
	{
		//找出左右孩子小的那个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		//若孩子的值大于父亲则交换,并将孩子下标给父亲,重新计算孩子下标
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		//如果孩子大,则说明为小堆,不需要向下调整
		else
		{
			break;
		}
	}
}

//堆排序
//1.升序建大堆
//2.降序建小堆
void HeapSort(int* a, int n)
{
	//建堆
	//假设树有N个节点,树高度:logN.时间复杂度:O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);//向下调整
	}

	int end = n - 1;//最后一个叶的下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]);

		AdjustDown(a, end, 0);
		--end;
	}
}

// 冒泡排序
void BubbleSort(int* a, int n)
{
	assert(a);
	int end = n;
	while (end > 0)
	{
		int exchange = 0;
		for (int i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}

		//如果一趟冒泡中没有发生交换,则说明已经有序,不需要冒泡
		if (exchange == 0)
		{
			break;
		}
	}
}

3.test.c

#include "Sort.h"

// 测试排序的性能对比
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	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);
	
	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];
	}

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

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

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

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

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


	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("BubbleSort:%d\n", end5 - begin5);
	

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
}

void TestInsertSort()
{
	int a[] = { 3,2,4,6,7,9,11,1,0 };
	PrintArray(a, sizeof(a) / sizeof(int));
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestShellSort()
{
	int a[] = { 9,8,7,6,5,4,3,2,1};
	PrintArray(a, sizeof(a) / sizeof(int));
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestSelectSort()
{
	int a[] = {5,4,7,6,4,2,9,7,8 };
	PrintArray(a, sizeof(a) / sizeof(int));
	SelectSort (a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestHeapSort()
{
	int a[] = { 1,8,4,7,6,3,9,12,6 };
	PrintArray(a, sizeof(a) / sizeof(int));
	HeapSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestBubbleSort()
{
	int a[] = { 7,8,1,14,6,10,2,12,9 };
	PrintArray(a, sizeof(a) / sizeof(int));
	BubbleSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}


int main()
{
	TestInsertSort();
	TestShellSort();
	TestSelectSort();
	TestHeapSort();
	TestBubbleSort();
	TestOP();
}

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

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

相关文章

【UE5.3 Cesium for Unreal】编译GlobePawn

【UE5.3 Cesium for Unreal】编译GlobePawn

目录 前言 效果 步骤 一、下载所需文件 二、下载CesiumForUnreal插件 三、处理下载的文件 四、修改代码 “CesiumForUnreal.uplugin”部分 “CesiumEditor.cpp”部分 “CesiumEditor.h”部分 “CesiumPanel.cpp”部分 “IonQuickAddPanel.cpp”部分 “IonQuickAd…
阅读更多...
线程的理解及基本操作

线程的理解及基本操作

目录 一、线程的理解 &#xff08;1&#xff09;什么是线程呢&#xff1f; &#xff08;2&#xff09;线程的优缺点及异常 二、线程的基本操作 &#xff08;1&#xff09;创建一个新的进程 &#xff08;2&#xff09;获取线程id &#xff08;3&#xff09;线程终止 &…
阅读更多...
SpringBoot 集成RabbitMQ 实现钉钉日报定时发送功能

SpringBoot 集成RabbitMQ 实现钉钉日报定时发送功能

文章目录 一、RabbitMq 下载安装二、开发步骤&#xff1a;1.MAVEN 配置2. RabbitMqConfig 配置3. RabbitMqUtil 工具类4. DailyDelaySendConsumer 消费者监听5. 测试延迟发送 一、RabbitMq 下载安装 官网&#xff1a;https://www.rabbitmq.com/docs 二、开发步骤&#xff1a;…
阅读更多...
AC的旁挂和直连的方式的使用场景

AC的旁挂和直连的方式的使用场景

AC组网架构 AC中文含义为无线接入控制器&#xff0c;主要功能是可以批量配置和管理无线AP。经常工作在大中型园区网络、企业办公网络等应用场景。 下面来介绍一下无线AC的几种经典架构。 一1旁挂式组网 旁挂式组网顾名思义&#xff0c;就是旁挂在网络中&#xff0c;对AP来进行…
阅读更多...
view design之table自定义单元格模版

view design之table自定义单元格模版

View Design之table自定义单元格模版 在 columns 的某列声明 slot 后&#xff0c;就可以在 Table 的 slot 中使用参数。 slot 的参数有 3 个&#xff1a;当前行数据 row&#xff0c;当前列数据 column&#xff0c;当前行序号 index。 完整示例 <template><Table …
阅读更多...
乘云而上，OceanBase再越山峰

乘云而上，OceanBase再越山峰

一座山峰都是一个挑战&#xff0c;每一次攀登都是一次超越。 商业数据库时代&#xff0c;面对国外数据库巨头这座大山&#xff0c;实现市场突破一直都是中国数据库产业多年夙愿&#xff0c;而OceanBase在金融核心系统等领域的攻坚克难&#xff0c;为产业突破交出一副令人信服的…
阅读更多...
在Ubuntu（Linux）系统下安装Anaconda3

在Ubuntu（Linux）系统下安装Anaconda3

1、到官网下载Linux版本的包&#xff1a;https://www.anaconda.com/download/success 2、到所在目录中&#xff0c;运行下方命令&#xff0c;Anaconda3-2024.06-1-Linux-x86_64.sh是下载包的名字 bash Anaconda3-2024.06-1-Linux-x86_64.sh输入yes确定 3、输入~/anaconda3/b…
阅读更多...
MySQL数据库集群-PXC方案视频教程下载 MySQL架构设计及常见业务处理

MySQL数据库集群-PXC方案视频教程下载 MySQL架构设计及常见业务处理

MySQL数据库集群-PXC方案视频教程下载 MySQL架构设计及常见业务处理30套数据库系列Mysql/SQLServer/Redis/Mongodb/Nosql精讲训练营项目实战&#xff0c;数据库设计&#xff0c;架构设计&#xff0c;性能管理&#xff0c;集群搭建&#xff0c;查询优化&#xff0c;索引优化&…
阅读更多...
Spring Boot植物健康系统：智慧农业的新趋势

Spring Boot植物健康系统：智慧农业的新趋势

6系统测试 6.1概念和意义 测试的定义&#xff1a;程序测试是为了发现错误而执行程序的过程。测试(Testing)的任务与目的可以描述为&#xff1a; 目的&#xff1a;发现程序的错误&#xff1b; 任务&#xff1a;通过在计算机上执行程序&#xff0c;暴露程序中潜在的错误。 另一个…
阅读更多...
经常聊架构模式，设计模式，编程模式，也谈谈“反模式”

经常聊架构模式，设计模式，编程模式，也谈谈“反模式”

在软件工程中&#xff0c;反模式&#xff08;Anti-Pattern&#xff09;是指那些表面上看起来是一个解决方案&#xff0c;但实际上会导致更多问题或者效果不佳的常见实践。它们可能在某些情况下被广泛使用&#xff0c;但实际上是无效甚至产生反效果的。 文档中并没有详细描述具…
阅读更多...
四、Prompt工程——简单应用

四、Prompt工程——简单应用

Prompt工程——简单应用 一、提示工程&#xff08;Prompt Engineering&#xff09;二、Prompt基本法则三、Prompt 调优四、简单的例子文本总结文本判断文本提取文本转化——翻译文本转化——语气 更多结语 一、提示工程&#xff08;Prompt Engineering&#xff09; 提示工程也…
阅读更多...
【华为HCIP实战课程二十五】中间到中间系统协议IS-IS配置实战续系统ID区域ID，网络工程师

【华为HCIP实战课程二十五】中间到中间系统协议IS-IS配置实战续系统ID区域ID，网络工程师

上章简单讲解了ISIS基本配置，本章继续详细讲解ISIS配置及实施 IS-IS配置拓扑 1、R1进行配置IS-IS [R1]display current-configuration configuration isis isis 1 network-entity 49.0124.1111.1111.1111.00 //配置NET地址，由三部分组成，区域ID、系统ID和固定的SEL 00 i…
阅读更多...
python道格拉斯算法的实现

python道格拉斯算法的实现

废话不多说 直接开干 需要用到模块 pip install -i https://pypi.tuna.tsinghua.edu.cn/simple math #对浮点数的数学运算函数 pip install -i https://pypi.tuna.tsinghua.edu.cn/simple shapely #提供几何形状的操作和分析&#xff0c;如交集、并集、差集等 pip install -i …
阅读更多...
如何保证自动化测试的可信性？

如何保证自动化测试的可信性？

对于自动化测试的可信性&#xff0c;这是一个与自动化测试ROI&#xff08;投资回报率&#xff09;紧密关联的关键问题。自动化测试的可信性&#xff0c;不仅关乎自动化的持续性和价值&#xff0c;更重要的是它是否能够准确、真实地反映产品的质量状态。 举例来说&#xff0c;假…
阅读更多...
鸿蒙开发-this指向+样式复用+代码调试

鸿蒙开发-this指向+样式复用+代码调试

​&#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;鸿蒙开发篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来鸿蒙开发篇专栏内容:鸿蒙开发-this指向样式复用代码调试 目录 一、this指向 1.原生 鸿蒙 this使用细节 -…
阅读更多...
windows下使用nvm进行多版本nodejs管理

windows下使用nvm进行多版本nodejs管理

目录 一&#xff1a;背景 二&#xff1a;nvm的介绍 三&#xff1a;环境切换使用 一&#xff1a;背景 最近在开发node js的项目&#xff0c;其中一个项目的前端和后台使用了两个node版本&#xff0c;因此需要不同的环境配置来进行开发任务&#xff0c;刚好nvm这个插件可以实现…
阅读更多...
vue使用高德地图实现轨迹显隐

vue使用高德地图实现轨迹显隐

<template><div><el-button type"primary" click"pathShowOrHide">轨迹显/隐</el-button><div id"container" /></div> </template><script> import AMapLoader from amap/amap-jsapi-loaderex…
阅读更多...
Linux基础环境搭建（CentOS7）- 安装Scala和Spark

Linux基础环境搭建（CentOS7）- 安装Scala和Spark

#Linux基础环境搭建&#xff08;CentOS7&#xff09;- 安装Scala和Spark Linux基础环境搭建&#xff08;CentOS7&#xff09;- 安装Scala和Spark 大家注意以下的环境搭建版本号&#xff0c;如果版本不匹配有可能出现问题&#xff01;&#xff08;spark不要下2.4版本的 会报错…
阅读更多...
MySQL 日志之 binlog 格式 → 关于 MySQL 默认隔离级别的探讨

MySQL 日志之 binlog 格式 → 关于 MySQL 默认隔离级别的探讨

开心一刻 image 产品还没测试直接投入生产时&#xff0c;这尼玛... 背景问题 再讲 binlog 之前&#xff0c;我们先来回顾下主流关系型数据库的默认隔离级别&#xff0c;是默认隔离级别&#xff0c;不是事务有哪几种隔离级别&#xff0c;别会错题意了 1、Oracle、SQL Server 的默…
阅读更多...
fastGpt

fastGpt

参考本地部署FastGPT使用在线大语言模型 1 rockylinx 1 ollama安装 在rockylinux中安装的&#xff0c;ollama由1.5G&#xff0c;还是比较大&#xff0c;所有采用在windows下下载&#xff0c;然后安装的方式&#xff0c;linux安装 tar -C /usr -xzf ollama-linux-amd64.tgz #…
阅读更多...
最新文章

Copyright @ 2022~2023