常见排序（C语言版）

🕗 发布于 2024-09-22 13:25 数据结构 c语言 学习排序算法算法

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]插入，原位置上的元素顺序后移。

特点：

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

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时，所有记录在统一组内排好序。

特点：

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

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个元素

特点：

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

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:堆排序在写树中的二叉树部分的应用有讲解，树）

特点：

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

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

hoare版本：
挖坑法：
前后指针版本：

快速排序特点：

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

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

2.3.4快速排序优化

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

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）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：

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

特点：

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

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基本思想

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

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

特点：

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

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.排序算法复杂度及稳定性分析

原文地址：https://blog.csdn.net/2301_80434764/article/details/142263388

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：联合和枚举
下一篇：动手学深度学习（李沐）PyTorch 第 2 章预备知识

React与AngularJS比较一二
其核心优势在于其组件化架构，这一设计哲学鼓励开发者构建可复用的UI组件，极大地提升了开发效率和代码的可维护性。React的虚拟DOM技术是其性能卓越的基石，通过智能地比较和更新DOM差异，实现了高效的
阅读更多2024-09-24
接口测试Postman关联，断言，前置，参数化用法
我们直接搜索Postman官网下载即可。
阅读更多2024-09-24
Kibana中突然看不到日志ElasticSearch突然采集不到日志问题解决分析
分片是 Elasticsearch 在集群中分发数据的关键。把分片想象成数据的容器。文档存储在分片中，然后分片分配到集群中的节点上。当集群扩容或缩小，Elasticsearch 将会自动在节点间迁移分
阅读更多2024-09-24
解构拼duoduo电商api数据海量详情商品自动化
综上所述，获取商品详情API数据的功能作用是多方面的，它不仅能够为商家提供全面的商品信息支持，还能够通过数据分析、实时监控等功能帮助商家优化运营策略、提升用户体验和市场竞争力。编写测试用例：根据 AP
阅读更多2024-09-24
kettle发邮件：使用Kettle实现自动化发信？
无论是企业内部的管理，还是对外的客户服务，Kettle发邮件都能为您带来显著的效率提升和成本节约。AokSend，集成API与SMTP，Kettle发邮件神器，自动化高效，信息传递无忧！
阅读更多2024-09-24
AIoT是什么？AIoT现状如何？
AIoT 即人工智能物联网（Artificial Intelligence & Internet of Things），是人工智能技术（AI）与物联网（IoT）在实际应用中的落地融合。物联网产
阅读更多2024-09-24
代码随想录Day17 图论-1
做图论这部分的题目DFS和BFS少不了DFS是深搜沿着一条路一直搜索下去直到无法继续向下再通过回溯换一条路进行搜索BFS是广搜就是从当前节点出发一直把当前节点所连接的所有节点都搜索过之后进
阅读更多2024-09-24
机器学习中分类问题的各类评估指标总结
召回率计算方式、适用场景、局限性。
阅读更多2024-09-24
滚动轴承故障诊断、预测与分类综合数据集
独家整理滚动轴承数据集故障诊断，预测、分类最全套数据集可做对比实验拍就发自动发货1.CWRU西储大学轴承数据集2.MFPT机械故障协会数据集3.XJTU西安交通大学数据集4.渥太华变速轴承轴
阅读更多2024-09-24
数据科学基石：解析属性类型体系——从标称到比率，全面洞察数据分类机制
本篇文章致力于系统阐述数据科学领域内关键的属性类型概念，从标称属性的独特地位，到序数属性的分级原则，直至区间属性与比率属性的量化标准，旨在为研究者与从业者提供一份详实且严谨的专业指南。值得注意的是，标
阅读更多2024-09-24