C语言实现八大排序算法

C语言实现八大排序算法

引用

CSDN

1.

https://blog.csdn.net/weixin_73629886/article/details/144366200

排序算法是计算机科学中的重要基础，广泛应用于数据处理和算法设计中。本文将详细介绍八大经典排序算法的原理、实现和性能特点，帮助读者全面掌握这些基本排序方法。

插入排序

直接插入排序

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

比如我们玩扑克牌的时候就选择了直接插入排序：

希尔排序

希尔排序是在直接插入排序之前，先进行预排序，使数组达到“相对有序”的状态再进行直接插入排序。即：

1. 将数组中每隔gap距离的数归为一组，将每组进行一次直接插入排序，然后将gap变小，继续对每组数据进行直接插入排序；
2. 直到gap=1时，进行直接插入排序。

选择排序

直接选择排序

直接选择排序是从待排序数据中每次选出最小或最大的元素，存放在序列的起始位置，直到全部数据排序完成为止；为了增加效率，在此基础上每次都选出序列中最大和最小的元素，将其放在序列的起始或末尾位置，直到全部数据排完为止。

堆排序

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

关于堆的概念，我们在数据结构7——二叉树的顺序结构以及堆的实现已经讲过，详情可以点击链接跳转，此处不再详细赘述。

关于堆排序的实现，我们同样在上述文章中已经实现过，只需将其AdjustDown(向下调整)函数引用过来即可，不过在那篇文章中我们实现的是小堆，我希望排序得到一个升序序列，那么我就需要建大堆，只需稍微修改即可；

第一次调用AdjustDown函数使数组变成大根堆，第二次调用AdjustDown函数完成数组的排序：

交换排序

冒泡排序

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

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

（为了方便，基准值一般选在序列的最左边或最右边）

Hoare版本

基本步骤为：

1. 选择序列最左边的值作为基准值keyi；
2. 确定left与right分别为序列的初始值和末尾值，令二者往序列中间走；
3. 让right先走，遇到比keyi小的值就停下(找小)，令left后走，遇到比keyi大的值就停下(找大)；
4. 二者都停下之后交换数据；
5. 重复③和④，直到right与left相遇；
6. 交换keyi与left的值。

此时被交换的keyi的值，即现在left的值已经到达了它该到达的位置。

（注：当left与right相遇时，相遇时刻的值一定比keyi小，这是③我们令right先走决定的，而right先走又是①我们令最左边的值作为基准值所决定的。

当然，当我们令序列最右边的值作为基准值时，就应该令left先走了，理所应当此时left与right相遇时的值也一定比keyi大。）

挖坑法

挖坑法与Hoare版本类似，具体步骤为：

1. 将序列最左边的值取出作为基准值key，值取出后，此时序列最左边留下“坑位”；
2. 确定left与right分别为序列的初始值和末尾值，令二者往序列中间走；
3. 让right先走，遇到比key小的值就停下(找小)，停下后将right位置的值取出去填“坑位”，此时right位置就留下“坑位”；
4. 令left后走，遇到比key大的值就停下(找大)，停下后将left位置的值取出去填“坑位”，此时left位置就留下“坑位”；
5. 重复③和④，直到right与left相遇，相遇的地点必定是“坑位”，此时用key去填“坑位”。

前后指针法

前后指针法具体步骤为：

1. 将序列最左边的值确定为基准值key，创建指针prev和cur(cur=prev+1)；
2. 先比较此时cur位置的值与key的大小，

• 若小于key，则prev++，然后交换prev与cur位置的值；
• 若cur不小于key，则prev保持不动；

3. cur++；
4. 重复②和③，直到cur超出序列范围为止；
5. 此时交换prev与key的值。

（应该注意的点：步骤笼统来说是：先prev++，再交换prev与cur，最后cur++）

快速排序优化

在介绍快速排序刚开始时我们就提到：“快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法”，这种排序算法类似于二叉树的先序遍历：以基准值为界，分左右两边进行递归。

可现在问题来了：

如果选择的基准值恰巧是序列中的最大值或最小值呢？

这时就会进行不必要的递归，更是在排序大量有序数据或者接近有序数据时，效率会比较低，甚至可能会出现程序崩溃的情况；

这是因为在排序有序数据时，快速排序的递归调用次数过多，会导致栈溢出的情况。

为了解决这种问题，有两种优化方法：

1. 三数取中选key值：
   即在序列的初始位置、中间位置、末尾位置的三个数中选出中间值作为key值；
2. 递归到小的子区间时，可以考虑使用插入排序。

非递归快速排序

在4中，我们优化了快速排序，为的就是减少快速排序的递归次数，可是尽管减少了递归次数，可是当数据足够足够大时，又不得不进行足够多次递归了。

递归次数足够多就有可能造成“爆栈”——栈溢出！的风险，以上四种方法都是递归式的快速排序，接下来介绍一种非递归的快速排序。

其实非递归快速排序基本思想同以上三种方法大体相同：

1. 取数据序列初和序列末的下标入栈；
2. 两次取出栈顶元素；
3. 调用一次Hoare版本的排序算法（挖坑法和前后指针法当然也可以），以获得“基准值”处的坐标；
4. 此时基准值已到达正确的位置，在此处将序列一分为左右两个序列；
5. 若左右两个序列有元素，则将左右序列的初始和末尾下标分别继续入栈；
6. 重复②③④⑤，直到栈为空停止。

归并排序

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

递归式归并排序

按照这种思想，是将一个序列分解为若干个有序的子序列，再将这若干个有序的子序列合并成一个有序的整序列，为了方便判断，直接将子序列分解到只剩一个元素，一个元素当然可以算作有序呀！

所以归并排序的基本步骤为：

1. 将整个序列平分（一分二，二分四......），直到序列只剩一个元素为止；
2. 将“同时分家”的两个子序列进行排序，排好序后，再“放回到他们的父亲家里”；
   （这里就可以创建一个临时数组tmp，按照两个子序列谁的元素小谁先入数组的原则排序，将排好序的tmp再拷贝回“父序列”）

非递归式归并排序

在讲非递归快速排序时，我们提到，递归存在一定风险，当数据足够足够多时可能会有爆栈的风险，因此这里就对归并排序提供了非递归的思路：

归并排序的思想就是分治法-先分解再合并，而以上代码发生递归的地方就是出现在分解过程，为了不递归，能不能绕过分解过程直接合并呢？

所以非递归的思想与递归的思想大致相同，不同的是，非递归思想是：

先让每一个元素为一组两两归并，再每两个元素为一组两两归并，再每四个元素为一组两两归并，再每八个......直到归并完所有元素为止。

计数排序

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

操作步骤：

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

（注：计数排序只适用于排列整数，当序列中既有正数又有负数时，则不适合用计数排序；另外，计数排序只适用于数据相对集中的序列，如：就排列三个数，99999999、1、2，数据跨度太大，就要开辟一个长度为99999999的数组，显然这是不合适的）

排序算法性能总结

所谓稳定性，举个例子就明白了：比如将一副扑克牌排序，排序之前红桃十在黑桃十的前面，排序之后红桃十依旧在黑桃十的前面，即序列中相同元素在排序前后相对位置不发生变化，就认为该排序算法稳定。

最后的最后，写一段程序对以上实现的所有排序进行简单的测试：

由测试结果可以看出，快排之所以敢叫快排，是因为其确实是有一定实力的，计数排序虽然应用场景比较少，但是在特定场景下确实是比较有优势的。