《C语言实现各种排序算法》

文章目录

    • 一、排序
        • 1、排序的各种方式分类
    • 二、插入排序
        • 1、直接插入排序
        • 2、希尔排序
        • 3、希尔排序时间复杂度分析
    • 三、选择排序
        • 1、直接选择排序
        • 2、堆排序
    • 四、交换排序
        • 1、冒泡排序
        • 2、快速排序
        • 3、快速排序hoare找基准值
        • 4、快排挖坑法找基准值
        • 5、前后指针法
        • 6、快速排序非递归实现
    • 五、归并排序
        • 1、递归实现
        • 2、非递归实现
    • 六、排序算法复杂度及稳定性分析
    • 七、计数排序

一、排序

在生活中各种场景中都会有排序的身影存在，在网购时会有价格排序，在学校中会有程序排序，在游戏中会有段位的排序等。

1、排序的各种方式分类

在这里插入图片描述

这些排序的效率各有不同

二、插入排序

直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列 。

1、直接插入排序

当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移

代码实现：

void InsertionSort(int* arr, int n)
{
	int i = 0;
	int j = 0;
	for ( i = 1; i < n; i++)
	{
		j = i-1;
		int tmp = arr[i];
		while (j >= 0)
		{
			if (arr[j] < tmp)
			{
				arr[j + 1] = arr[j];
				j--;
			}
			else
			{
				break;
			}
		}
		arr[j + 1] = tmp;
	}
}
2、希尔排序

直接插入排序效率不高，在直接插入排序的基础上进行优化，改进，把一个大的集合分为若干个小的集合再进行直接插入排序，从而提升效率。
希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序。

代码实现：

void ShellSort(int* arr, int n)
{
	int gec = n;
	int i, j = 0;
	while (gec > 1)
	{
		gec = gec / 3 + 1;
		for (i = gec; i < n; i++)
		{
			j = i - gec;
			int tmp = arr[i];
			while (j >= 0)
			{
				if (arr[j] < tmp)
				{
					arr[j + gec] = arr[j];
					j -= gec;
				}
				else
				{
					break;
				}
			}
			arr[j + gec] = tmp;
		}
	}
}
3、希尔排序时间复杂度分析

外层循环的时间复杂度可以直接给出为： O(log2 n) 或者 O(log3 n) ，即 O(log n)
内层循环：

在这里插入图片描述
在这里插入图片描述

希尔排序的时间复杂度大约为 log ⁡ 2 n 1.3 \log_2 {n^{1.3}} log2​n1.3

三、选择排序

每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

1、直接选择排序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int max = begin, min = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[min])
			{
				min = i;
			}
			if (a[i] > a[max])
			{
				max = i;
			}
		}
		if (max == begin)
		{
			max = min;
		}
		{
			int tmp = a[min];
			a[min] = a[begin];
			a[begin] = tmp;
		}
		{
			int tmp = a[max];
			a[max] = a[end];
			a[end] = tmp;

		}
		begin++;
		end--;
	}
}
2、堆排序
void HeapSort(int* arr, int n)
{
	int i = 0;
	for (i = (n-1)/2; i>=0; i--)
	{
		
		int parent = i;
		int child = parent * 2 + 1;
		while (child <= i)
		{
			if (child + 1 <= i && arr[child + 1] < arr[child])
			{
				child++;
			}
			if (arr[child] < arr[parent])
			{
				int tmp = arr[parent];
				arr[parent] = arr[child];
				arr[child] = tmp;
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}

	}
	for (i = n - 1; i > 0; i--)
	{
		int child = i;
		int parent = 0;
		int tmp = arr[parent];
		arr[parent] = arr[child];
		arr[child] = tmp;
		child = parent * 2 + 1;
		while (child < i)
		{
			if (child + 1 < i && arr[child + 1] < arr[child])
			{
				child++;
			}
			if (arr[child] < arr[parent])
			{
				tmp = arr[parent];
				arr[parent] = arr[child];
				arr[child] = tmp;
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
}

堆排序的时间复杂度为n log ⁡ n \log n logn

四、交换排序

1、冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int falg = 1;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				falg = 0;
			}
		}
		if (falg)
		{
			break;
		}
	}
}
2、快速排序

通过找基准值，基准值的位置就是这个值该待的位置，然后递归找基准值左边区间和右区间，直到区间不成立位置，确定每个值该待的位置完成排序。

int _QuickSort(int* a, int left, int right)
{
	int keyi = left;
	left++;
	while (left <= right)
	{
		
 		while (left <= right && a[left] < a[keyi])
		{
			left++;
		}
		while (left <= right && a[right] > a[keyi])
		{
			right--;
		}
		if (left <= right)
		{
			int tmp = a[left];
			a[left] = a[right];
			a[right] = tmp;
			left++;
			right--;
		}

	}
	int tmp = a[keyi];
	a[keyi] = a[right];
	a[right] = tmp;

	return right;
}

void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	
	int keyi = _QuickSort(a, left, right);
	QuickSort(a, keyi + 1, right);
	QuickSort(a, left, keyi - 1);

}

快排的空间复杂度：O( l o n g n long n longn)
快排的时间复杂度：O(n l o n g n long n longn)

3、快速排序hoare找基准值
 //快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	++left;
	while (left < right)
	{
		while (left <=right && a[right] > a[keyi])
		{
			right--;
		}
		while (left <= right && a[left] < a[keyi])
		{
			left++;
		}
		if (left < right)
		{
			swap(&a[left], &a[right]);
		}
	}
	swap(&a[keyi], &a[right]);

	return right;
}
4、快排挖坑法找基准值
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	int hole = left;
	int tmp = a[hole];
	while (left < right)
	{
		while (left < right && a[right] > tmp)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] < tmp)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = tmp;
	return hole;
}
5、前后指针法
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	int pfast = left + 1;
	int pslow = left;
	int keyi = left;
	while (pfast <= right)
	{
		while (pfast <= right && a[pfast] < a[keyi] && ++pslow != pfast)
		{
			swap(&a[pslow], &a[pfast]);
		}
		pfast++;
	}
	swap(&a[pslow], &a[keyi]);
	return pslow;
}
6、快速排序非递归实现
// 快速排序 非递归实现

//运用栈数据结构
typedef int StackDataType;

typedef struct Stack
{
	int* a;
	int capacity;
	int top;
}ST;

//栈初始化
void STInit(ST* ps)
{
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

//入栈
void STPush(ST* ps,StackDataType x)
 {
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		int* tmp = (int*)realloc(ps->a, newcapacity * sizeof(StackDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
		tmp = NULL;
	}
	ps->a[ps->top++] = x;
}

//判断栈是否为空
bool STEmpty(ST* ps)
{
	return ps->top == 0;
}

//出栈
void STPop(ST* ps)
{
	if (ps->top == 0)
	{
		return;
	}
	ps->top--;
}

//取栈顶元素
StackDataType STTop(ST* ps)
{
	if (ps->top == 0)
	{
		exit(1);
	}
	return ps->a[ps->top - 1];
}

void QuickSortNonR(int* a, int left, int right)
{
	ST s;
	STInit(&s);

	STPush(&s, right);
	STPush(&s, left);
	while (!STEmpty(&s))
	{
		int begin = STTop(&s);
		STPop(&s);
		int end = STTop(&s);
		STPop(&s);


		int pfast = begin + 1;
		int pslow = begin;
		int keyi = begin;
		while (pfast <= end)
		{
			while (pfast <= end && a[pfast] < a[keyi] && ++pslow != pfast)
			{
				swap(&a[pslow], &a[pfast]);
			}
			pfast++;
		}
		swap(&a[pslow], &a[keyi]);

		if (pslow + 1 < end)
		{
			STPush(&s, end);
			STPush(&s, pslow + 1);
		}
		if (pslow - 1 > begin)
		{
			STPush(&s, pslow - 1);
			STPush(&s, begin);
		}
	}

五、归并排序

归并排序算法思想：
归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（DivideandConquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。

1、递归实现

在这里插入图片描述

代码实现：

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	int mid = (right - left) / 2 + left;

	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right,tmp);

	//合并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int begin = left;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[begin++] = arr[begin1++];
		}
		else
		{
			tmp[begin++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[begin++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[begin++] = arr[begin2++];
	}

	//传值
	while (left <= right)
	{
		arr[left] = tmp[left];
		left++;
	}
}

void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}
2、非递归实现
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(1);
	}

	int k = 1;
	while (k < n)
	{
		int i = 0;
		for (i = 0; i < n - 2 * k + 1;i += 2*k)
		{
			int mid = i + k - 1;
			int left = i;
			int right = i + 2 * k - 1;

			int begin1 = left, end1 = mid;
			int begin2 = mid + 1, end2 = right;

			int begin = left;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[begin++] = a[begin1++];
				}
				else
				{
					tmp[begin++] = a[begin2++];
				}
			}

 			while (begin1 <= end1)
			{
				tmp[begin++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[begin++] = a[begin2++];
			}

			while (left <= right)
			{
				a[left] = tmp[left];
				left++;
			}
		}

		if (i < n-k)
		{
			int mid = i+k-1;
			int left = i;
			int right = n-1;

			int begin1 = left, end1 = mid;
			int begin2 = mid + 1, end2 = right;

			int begin = left;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[begin++] = a[begin1++];
				}
				else
				{
					tmp[begin++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[begin++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[begin++] = a[begin2++];
			}

			while (left <= right)
			{
				a[left] = tmp[left];
				left++;
			}
		}
		k *= 2;
	}

	free(tmp);
}

六、排序算法复杂度及稳定性分析

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

在这里插入图片描述

七、计数排序

只能排序整数，不适合排不集中的数据如1,10000000,100000002；会产生空间浪费

// 计数排序
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (min > a[i])
		{
			min = a[i];
		}
		if (max < a[i])
		{
			max = a[i];
		}
	}

	int range = max - min + 1;
	int* count = (int*)calloc(range ,sizeof(int));
	for (int i = 0; i < n; i++)
	{
		count[a[i]-min]++;
	}
	int indext = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[indext++] = i + min;

		}
	}

	free(count);
	count = NULL;
}

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

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

相关文章

Mysql的相关编程基础知识

Mysql的相关编程基础知识

一. 配置MySQL 首先下载mysql-5.0.96-winx64&#xff0c;安装过程如下图所示。 1.安装MySQL 5.0 ​ ​ 2.选择手动配置、服务类型、通用多功能型和安装路径 ​ 3.设置数据库访问量连接数为15、端口为3306&#xff08;代码中设置URL用到&#xff09;、编码方式为utf-8 ​ 4.设…
阅读更多...
使用Seaborn绘制热力图

使用Seaborn绘制热力图

热力图是一种用于展示矩阵数据的图表&#xff0c;其中颜色深浅表示数据值的大小。 import seaborn as sns import numpy as np import matplotlib.pyplot as plt # 创建示例数据 data np.random.rand(10, 12) # 绘制热力图 sns.heatmap(data, annotTrue, cmapcoolwa…
阅读更多...
【故障处理】- ping不通的原因

【故障处理】- ping不通的原因

PING不通是一个非常常见的网络问题&#xff0c;它可能由多种原因引起。如链路故障、ARP学习失败等 以一个Ping不通的尝试示例&#xff0c;介绍Ping不通故障的定位思路。如下图&#xff1a; PC3 Ping不通PC4 PC>ping 20.1.1.20Ping 20.1.1.20: 32 data bytes, Press Ctrl_C…
阅读更多...
全新分支版本！微软推出Windows 11 Canary Build 27686版

全新分支版本！微软推出Windows 11 Canary Build 27686版

已经很久没有看到 Windows 11 全新的分支版本了&#xff0c;今天微软发布 Windows 11 Canary 新版本&#xff0c;此次版本号已经转移到 Build 27xxx&#xff0c;首发版本为 Build 27686 版。 此次更新带来了多项改进&#xff0c;包括 Windows Sandbox 沙盒功能切换到 Microsof…
阅读更多...
目标检测中的IOU（Intersection over Union）算法是什么？

目标检测中的IOU（Intersection over Union）算法是什么？

目标检测中的IOU&#xff08;Intersection over Union&#xff09;算法是什么&#xff1f; IOU&#xff0c;即交并比&#xff0c;是目标检测中用于评估预测边界框与真实边界框重叠程度的重要指标。它的计算公式为&#xff1a; IOU Area of Intersection Area of Union \text{…
阅读更多...
学习大数据DAY40 基于 hive 的数据处理

学习大数据DAY40 基于 hive 的数据处理

目录 Hive 复合数据定义方法 Hive 复合数据查询方法 hive 内置函数 上机练习 Hive 复合数据定义方法 Hive 复合数据查询方法 hive 内置函数 -- 查看系统自带的函数 show functions; -- 显示自带的函数的用法 desc function upper; -- 详细显示自带的函数的用法 desc …
阅读更多...
【Linux基础】Linux中的开发工具(1)--yum和vim

【Linux基础】Linux中的开发工具(1)--yum和vim

目录 ✈️前言一&#xff0c;Linux 软件包管理器 yum1. 什么是软件包2. 如何安装软件3. 如何卸载软件 二&#xff0c;Linux编辑器-vim使用1. vim的基本概念1.1 命令/正常/普通模式1.2 插入模式1.3 底行模式 三&#xff0c;vim命令模式命令集1. 移动光标2. 删除字符3. 复制4. 替…
阅读更多...
JSONP跨域访问漏洞

JSONP跨域访问漏洞

目录 JSONP跨域访问漏洞 课程目标 一、漏洞一&#xff1a;利用回调GetCookie 二、漏洞二&#xff1a;利用CSRF获取数据 三、JSON攻击防御方案 课程目标 1、理解JSONP跨域访问漏洞原理 2、掌握JSONP跨域访问的防御方案 一、漏洞一&#xff1a;利用回调GetCookie 说变了…
阅读更多...
跨平台无缝编辑，2024年免费视频剪辑工具全解析

跨平台无缝编辑，2024年免费视频剪辑工具全解析

在众多视频剪辑工具中&#xff0c;免费视频剪辑软件凭借其易用性、功能丰富性以及零成本的优势&#xff0c;赢得了广大用户的青睐。今天&#xff0c;就让我们一起盘点那些2024年大家都在用的免费视频剪辑软件&#xff0c;探索它们如何助力我们轻松实现创意梦想。 1.福昕视频剪…
阅读更多...
基于Sringboot+Vue个人驾校预约管理系统--论文pf

基于Sringboot+Vue个人驾校预约管理系统--论文pf

TOC springboot503基于SringbootVue个人驾校预约管理系统--论文pf 第1章 绪论 1.1选题动因 当前的网络技术&#xff0c;软件技术等都具备成熟的理论基础&#xff0c;市场上也出现各种技术开发的软件&#xff0c;这些软件都被用于各个领域&#xff0c;包括生活和工作的领域。…
阅读更多...
多平台编译libexif

多平台编译libexif

下载地址&#xff1a;https://github.com/libexif/libexif/releases 1. ubuntu x64 &#xff08;银河麒麟系统aarch64步骤相同&#xff09; # 解压 > tar -jxvf libexif-0.6.24.tar.bz2 > cd libexif-0.6.24 # 配置 > ./configure # 编译 > make # 安装 > mak…
阅读更多...
openstack基本操作

openstack基本操作

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…
阅读更多...
Shell参考 - Linux Shell 训练营

Shell参考 - Linux Shell 训练营

出品方<Linux.cn & 阿里云开发者学堂> 一&#xff0c;Linux 可以划分为以下四个部分&#xff1a; 1. 应用软件 2. 窗口管理软件 Unity Gnome KDE 3. GNU 系统工具链 Software- GNU Project - Free Software Foundation 4. Linux 内核 二&#xff0c;什么是shell 1. L…
阅读更多...
ArcGIS高/低聚类(Getis-Ord General G)——探究人口空间格局的20年变迁

ArcGIS高/低聚类(Getis-Ord General G)——探究人口空间格局的20年变迁

先了解什么是莫兰指数高/低聚类莫兰指数&#xff1f; 高/低聚类 (Getis-Ord General G) 统计是一种用于检测空间数据中是否存在高值或低值聚类的统计方法&#xff0c;这种方法可以帮助我们理解数据点在空间上是否呈现某种聚集模式。 高/低聚类 (Getis-Ord General G) 和空间自…
阅读更多...
centos系统配置转发和iptables使之成为网关

centos系统配置转发和iptables使之成为网关

centos系统配置转发和iptables使之成为网关 在当下互联网环境中&#xff0c;有很多内网服务器不能出网&#xff0c;例如安装软件包&#xff0c;更新程序之类的&#xff0c;偶尔会需要出网&#xff0c;下面这种方式就是专门解决这个事情的。 如下配置在 centos 6 7 8 rocky 8 …
阅读更多...
期权的集合竞价是什么？期权集合竞价时间分享

期权的集合竞价是什么？期权集合竞价时间分享

今天带你了解期权的集合竞价是什么&#xff1f;期权集合竞价时间分享。期权的集合竞价是指在交易日的特定时间段内&#xff0c;期权合约的买卖双方提交并匹配他们的买卖意愿&#xff0c;以确定期权的开盘价格。 期权的集合竞价是一种特定的交易机制&#xff0c;用于确定期权合…
阅读更多...
位图与布隆过滤器 —— 海量数据处理

位图与布隆过滤器 —— 海量数据处理

&#x1f308; 个人主页&#xff1a;Zfox_ &#x1f525; 系列专栏&#xff1a;C从入门到精通 目录 &#x1f680; 位图 一&#xff1a; &#x1f525; 位图概念 二&#xff1a; &#x1f525; 位图的实现思路及代码实现三&#xff1a; &#x1f525; 位图的应用四&#xff1a;…
阅读更多...
文书智能助手

文书智能助手

背景 司法、医疗等行业存在着大量的文书&#xff0c;一份文书或者卷宗少则几十页&#xff0c;多则几万页。在查看和检查这些文书时&#xff0c;会遇到大量的信息。当需要查询进一步的详细内容时&#xff0c;往往需要选择一下文字&#xff0c;然后再在各种系统中 查询详细的信息…
阅读更多...
IDEA安装和使用（配图）

IDEA安装和使用（配图）

功能强大&#xff1a; 1、强大的整合能力&#xff0c;比如Git,Maven,Spring等 2、开箱即用&#xff08;集成版本控制系统&#xff0c;多语言支持的框架随时可用&#xff09; 3、符合人体工程学 1、高度智能 2、提示功能的快速&#xff0c;便捷&#xff0c;范围广 3、好用…
阅读更多...
Nginx平滑升级与回滚示例

Nginx平滑升级与回滚示例

Nginx 的平滑升级和平滑回滚是确保 Web 服务高可用性的重要组成部分。这两种操作允许你在不中断服务的情况下更新或回滚 Nginx 的版本。 Nginx 平滑升级与回滚 Nginx 的平滑升级和平滑回滚是确保 Web 服务高可用性的重要组成部分。这两种操作允许你在不中断服务的情况下更新或…
阅读更多...
最新文章

Copyright @ 2022~2023