当前位置： 首页 > article >正文

常见排序（C语言版）

article 2024/11/18 2:58:26

1.排序的概念及其应用

1.1排序的概念

排序：​ 在计算机科学与数学中，一个排序算法（英语：Sorting algorithm）是一种能将一串资料依照特定排序方式排列的算法。

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

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

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

排序的常见方法：插入、交换、选择、合并等等。

1.2排序的应用

排序在生活中无处不在，比如购物时对价格筛选、销量筛选等都用到排序，游戏中各个英雄的国服榜单等。排序算法也用在处理文字资料以及产生人类可读的输出结果。

注：虽然排序算法是一个简单的问题，但是从计算机科学发展以来，在此问题上已经有大量的研究。举例而言，冒泡排序在1956年就已经被研究。虽然大部分人认为这是一个已经被解决的问题，有用的新算法仍在不断的被发明。（例子：图书馆排序在2004年被发表）。

1.3常见的排序算法

2.常见排序算法实现

2.1插入排序

2.1.1基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的数据按值的大小逐个插入到一个已经排好序的有序序列中，直到所有的数据插入完为止，得到一个新的有序序列。

类似于平时玩的扑克牌的思想（摸牌的时候，摸一张就插入之前已经排好的序列中）

2.1.2直接插入排序

当插入第i（i >= 1）个元素时，前面的array[0]，array[1]，……，array[i-1]已经排好序，此时用array[i]的排序码与array[i-1]，array[i-2]……的排序码进行比较，找到插入位置即将array[i]插入，原位置上的元素顺序后移。

特点：

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

2.1.3直接插入排序代码实现

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 (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end+1] = tmp;
	}
}

2.1.4希尔排序（缩小增量排序）

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数（gap），把待排序文件中所有数据（n个数据）分成n / gap个组，所有距离为整数（gap）的数据分在同一组内，并对每一组内的数据进行排序。然后，重复上述分组和排序的工作。当整数（gap）到达 = 1时，所有记录在统一组内排好序。

特点： 

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

 2.1.5希尔排序代码实现

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 (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
						break;
				}
				a[end + gap] = tmp;
			}
	}

}

2.2选择排序

2.2.1基本思想

每一次从待排的数据元素中选出最小（或者最大）的一个元素，存放在序列的起始位置，知道全部待排元素的数据元素排完。

2.2.2直接选择排序

  • 在元素集合array[i]---array[n-1]中选择关键码最大（最小）的数据元素
  • 若它不是这组元素的最后一个（第一个）元素，则将它与这组元素的最后一个（第一个）元素交换
  • 在剩余的array[i]---array[n-2]集合中，重复上述步骤，直到集合剩余1个元素

 特点：

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

 2.2.3直接选择排序代码实现

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

注：代码实现的是同时选择最大和最小的数据元素，然后分别和数组尾部和头部交换

 2.2.4堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。（ps:堆排序在写树中的二叉树部分的应用有讲解，树）

​

 特点：

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

2.3交换排序

2.3.1基本思想

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排
序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。 ​

2.3.2冒泡排序代码实现

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

​ 2.3.3快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。将区间按照基准值划分为左右两半部分的常见方式有：

  1. hoare版本：
    ​
  2. 挖坑法：
  3. 前后指针版本：

 快速排序特点：

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

注：在hoare版本中，选取key的时候，需要注意选左边做key，要让右边先走；右边做key，要让左边先走 ，这样才能保证交换key和相遇点的时候不会出现顺序混乱的情况。具体原因如下：

2.3.4快速排序优化

  1. 三数取中法选key
  2. 递归到小的子区间时，可以考虑使用插入排序 

2.3.5快速排序非递归

 在数据量很大的时候，递归可能会有栈溢出的风险，并且速度也有所减慢，因此可以在原有的基础上加以改进，改为非递归。在递归的时候，递归主要就是存储对应的区间对应的下标，因为执行的语句都是相同的，就是分割不同的区间，传递不同的参数，所以可以用一个类似于后递归先处理的这样的逻辑的数据结构来存储对应的下标，没错，就是栈，每次入栈的时候，将要分割的区间对应的下标入栈（区间是两个下标，就一次性入两个，出两个），出栈即可。

2.3.6快速排序代码实现：

int GetMid(int* a,int left,int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		// left midi right
		if (a[midi] < a[right])
		{
			return midi;
		}
		// left right midi 
		else if (a[left] < a[right])
		{
			return right;
		}
		// right left midi
		else
			return left;
	}
	if (a[left] > a[midi])
	{
		// right midi left
		if (a[midi] > a[right])
		{
			return midi;
		}
		// midi right left
		else if (a[right] < a[left])
		{
			return right;
		}
		//midi left right
		else
			return left;
	}
}
int QSortPart1(int* a,int left,int right)
{
	//三数取中-->取合适的key
	int midi = GetMid(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	int start = left;
	int end = right;
	while (start < end)
	{
		//左边找小
		while (a[end] >= a[keyi] && start < end)
		{
			end--;
		}
		//右边找大
		while (a[start] <= a[keyi] && start < end)
		{
			start++;
		}
		Swap(&a[start], &a[end]);
	}
	Swap(&a[start], &a[keyi]);
	return start;
}
//前后指针
int QSortPart2(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while(cur <= right)
	{
		if (a[cur] < a[keyi] && a[cur] != a[++prev])
		{
			Swap(&a[cur], &a[prev]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	if (left > right)
		return;

	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right-left+1);
	}
	else
	{
		int keyi = QSortPart1(a, left, right);
		//int keyi = QSortPart2(a, left, right);
		//[left , keyi-1]  keyi  [key+1,right]
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}
//非递归快速排序
void QuickSortNonR(int* a, int left, int right)
{
	ST tmp;
	StackInit(&tmp);

	StackPush(&tmp, right);
	StackPush(&tmp, left);
	while(!StackEmpty(&tmp))
	{
		int start = StackTop(&tmp);
		StackPop(&tmp);
		int end = StackTop(&tmp);
		StackPop(&tmp);

		int keyi = QSortPart1(a, start, end);
		//[left , keyi-1]  keyi  [key+1,right]
		if (keyi + 1 < end)
		{
			StackPush(&tmp, end);
			StackPush(&tmp, keyi + 1);
		}
		if (start < keyi - 1)
		{
			StackPush(&tmp, keyi - 1);
			StackPush(&tmp, start);
		}
	}
	StackDestroy(&tmp);
}

2.4归并排序

2.4.1基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

注：在划分区间的时候，要特别注意下面的情况

特点：

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

2.4.2归并排序非递归

归并排序递归采用的是分割成两个有序的子区间，然后再合并，是在递归返回的过程中有序，所以在用非递归实现的时候，如果用栈模拟，那就需要用两个栈存放两个子区间的下标，然后再出栈，比较等。但是，采用两层循环就能很好地解决问题，将数据同样的分为n / gap组，每组gap个数据，然后两两合并，特别注意控制好分割的时候会不会越界即可。

 2.4.3归并排序代码实现

void _MergeSort(int* a, int* tmp, int start, int end)
{
	if (start >= end)
		return;
	int midi = (start + end) / 2;

	//[start1,midi] [midi+1,end1]
	_MergeSort(a, tmp, start, midi);
	_MergeSort(a, tmp, midi + 1, end);

	int start1 = start, end1 = midi;
	int start2 = midi + 1, end2 = end;
	int i = start;

	while (start1 <= end1 && start2 <= end2)
	{
		tmp[i++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
	}
	//处理一边比较小全部进完，另一边还没有进完的情况
	while (start1 <= end1)
	{
		tmp[i++] = a[start1++];
	}
	while (start2 <= end2)
	{
		tmp[i++] = a[start2++];
	}
	memcpy(a+start, tmp+start, (end-start+1)*sizeof(int));
}
void MergeSort(int* a, int n)
{
	int start = 0, end = n - 1;
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, tmp, 0, n-1);
	free(tmp);	
    tmp = NULL;
}

//归并排序非递归
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	//gap是每组数据个数
	int gap = 1;
	while(gap<n)
	{
		//i是每组归并的起点
		for (int i = 0; i < n; i += 2 * gap)
		{
			int start1 = i, end1 = i + gap - 1;
			int start2 = i + gap, end2 = i + 2 * gap - 1;
			int j = i;

			if (end1 > n-1 || start2 > n-1)
			{
				break;
			}
			if (end2 > n - 1)
			{
				end2 = n - 1;
			}
			while (start1 <= end1 && start2 <= end2)
			{
				tmp[j++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
			}
			//处理一边比较小全部进完，另一边还没有进完的情况
			while (start1 <= end1)
			{
				tmp[j++] = a[start1++];
			}
			while (start2 <= end2)
			{
				tmp[j++] = a[start2++];
			}
			memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}

2.5非比较排序

2.5.1基本思想

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

  1. 统计相同元素出现次数
  2. 根据统计的结果序列回收到原来的序列中

 特点：

  1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
  2. 时间复杂度：O(MAX(N,范围))
  3. 空间复杂度：O(范围)
  4. 稳定性：稳定

 2.5.2计数排序代码实现

void CountSort(int* a, int n)
{
	//找出数组最大最小，确定范围
	int min = a[0];
	int max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}

		if (a[i] > max)
		{
			max = a[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail");
		return;
	}
	//count数组与a数组映射的相对位置的下标++
	for (int j = 0; j < n; j++)
	{
		count[a[j] - min]++;
	}
	//回到原数组
	int k = 0;
	for (int l = 0; l < range; l++)
	{
		while (count[l]--)
		{
			a[k++] = l + min;
		}
	}
}

 

3.排序算法复杂度及稳定性分析 


http://www.kler.cn/a/320887.html

相关文章：

  • ElasticSearch学习笔记二：使用Java客户端
  • 深度学习中的Pixel Shuffle和Pixel Unshuffle：图像超分辨率的秘密武器
  • 神经网络的正则化(一)
  • YOLOv5、YOLOv6、YOLOv7、YOLOv8、YOLOv9、YOLOv10、YOLOv11 推理的 C++ 和 Python 实现
  • C++各类函数评点+详解
  • node对接ChatGpt的流式输出的配置
  • C# lambda表达式的几个案例
  • keepalived实战演练
  • Sealos 快速创建k8s 集群
  • 代码随想录算法训练营DAY09之动态规划（一）基础题目
  • 稀土功能化合物
  • HTML中的列表、表格、媒体元素和内联框架
  • 【C++习题】2.双指针_移动零
  • Rapid品牌SSL证书通配符单域名申请窍门
  • [笔记]数据结构
  • selenium模块的基本使用
  • 【Elasticsearch系列廿二】特殊参数
  • 【openwrt-21.02】openwrt PPTP Passthrough 不生效问题解决方案
  • Delphi5利用DLL实现窗体的重用
  • Vue 响应式监听 Watch 最佳实践
  • C++：STL详解（二）string类的模拟实现
  • 《python语言程序设计》2018版第8章18题几何circle2D类（下部）
  • 2024准备去面试软件测试岗，高频面试题预测？
  • yarn : 无法加载文件 C:\Users\Rog\AppData\Roaming\npm\yarn.ps1，因为在此系统上禁止运行脚本
  • 深入浅出 AbstractQueuedSynchronizer (AQS)
  • SpringCloudEureka简介