本系列文章将主要介绍数据结构中排序的相关知识：包括排序的概念及应用、常见排序算法的实现、排序算法复杂度及稳定度分析等内容。
一、常见的排序算法
1.插入排序
基本思想：把待拍戏的记录按其关键码值的大小逐个插入到一个已经排好序的有序数列中，知道所有的记录插入完为止，得到一个新的有序数列，比如我们在生活中的扑克牌，拿到一副牌我们需要按顺序排列好。
我们给定一个数组，当插入第i个元素时，前面的元素已经排好序，此时用插入元素与前面的元素由近到远进行比较，找到位置并插入，并把在此之后的元素后移。
接下来我们实现一下这个函数：我们假设有一个有序数组，现在在末尾元素的后面插进来一个元素，通过排序的方式，使整个数组再次有序，代码如下：
现在调整一下，给你一个无序数组，我们怎么把它重新排序呢？很简单，只需要把end的起始位置改一下即可。end起始是0，把后面的元素依次看成新插入的元素进行排序，那么就是一层循环，我们在此代码的基础上修改一下即可：
注意for循环的结束条件，n为元素个数，n-1是最后一个元素的下标，而我们最终要到倒数第二个元素终止循环（否则要是到倒数第一个元素结束循环，end+1就会越界访问），也可以写成end<=n-2。
很明显，插入排序的时间复杂度是O(N^2)(不可看循环个数判断，最坏的情况就是逆序，次数是1+2+3....+n-1,等差数列求和就是n^2)。
2. 冒泡排序
这个相对就简单一点，就是前一个与后一个相比不满足条件就交换。每一次循环结束都能把数组中最小的元素排在最后，所以我们只需要控制结束条件即可。
但是如果数组已经有序，我们此时就不需要再遍历，因此我们可以进行一下修改。
冒泡排序的时间复杂度也是O(N^2)。
3.堆排序
由于作者在二叉树系列文章讲过，就不多说了，请参考我前面的文章“二叉树（3）”。
4.希尔排序
其实，虽然插入排序与冒泡排序的时间复杂度一样，但当数据量很大的时候，插入排序的速度要远大于冒泡排序，希尔就研究其中的原因，他发明了一种新的排序办法提高效率，称为希尔排序。
原理：第一步：预排序，将整个数组分成以gap为间距的若干组，并把每一组分别进行插入排序，目的是让大的数可以更快地换到后面，小的更快换到前面，假设gap=3，我们以前面的数组为例：
（1）把567进行插入排序（2）把321进行插入排序（3）把948进行插入排序
（这里的每组插入排序只改变每组内元素的位置，不会对其他组元素的位置产生影响，比如3***2***1排序后是1***2***3而不是123******）（*是大数组内其他元素）
三次排序的结果就是5,1,4,6,2,8,7,3,9。我们先实现一下预排序：
其实和插入排序一样，只不过中间多了几个间隔，而且多了一层for循环，这层循环就是为了使每一个分组都进行插入排序，如果不加这层只能将一个分组进行插入排序，而我们一共有gap个分组
但我们可以对这个代码进行优化一下，也就是只要两层循环也可以，但我们需要改变一下条件：
改进后的代码的插入顺序改变了，之前是以每个分组进行整体排序，即这组排序完成后再排下一组，而改进后的代码是交替排序。（以上图数组为例）即56排完32排，然后98排，然后67所对应的位置再排。（如果67未因前几次的排序改变那就是67排）
当gap=1那就是正常的插入排序，gap越大，数据跳的越快，但越不接近有序。gap越小，数据跳的越慢，越不接近有序。所以我们需要权衡gap大小的问题，有一个很巧妙的方法，我们给出一个循环：
int gap=n;(n为数组大小）
while(gap>1)
{
gap=gap/3+1;(将刚才的预排序代码放在这里）
}
5.直接选择排序
在数组中遍历找到最大（小）的数放在指定位置，假定我们定第一个数最大，用这个最大的数依次与数组其他元素比较，如果发现有更大的那么定义更大的数为最大，最后放在数组的某一个位置即可。但是我们可以在此基础上对代码思路加以改进，原思路是每次找一个元素进行遍历，新思路就是一次找两个元素，一个最大一个最小，分别放在两端。
*6.快速排序
在此之前，我们介绍一下单趟排序。
什么是单趟排序，假设现在有一个数组，我们用一个关键词记录数组一个元素的下标（通常为第一个，假设关键词为key），然后我们分别再用两个变量存储数组两端元素的下标，假设我们要按升序排列，让两端的下标分别向中间走，先让右边走，如果右边当前下标的元素小于等于key，此时右端停止向前走，左端开始向后走，直到左端下标的元素大于等于key，让左右端的元素交换。直到二者相遇，此时将相遇的元素与key交换。这就是单趟排序，接下来我们用图片解释一下原理。
key与L记录第一个元素的位置，R记录了最后一个元素的位置，移动开始：
R记录的是8大于key向左走，此时记录的是10，继续向左走，来到了5小于key，此时R不动，L向右走，发现是1小于key继续向右走，直到遇见了7大于key，此时L不动，将L与R的元素互换，此时数组的元素顺序为6 1 2 5 9 3 4 7 10 8，完成一次交换后，R继续向左走，找到小于等于key的地方再停然后再让L走，发现9和4也会交换，此时R继续向左走，是3又停，再让L走以后发现二者在3的地方相遇，此时将key与3交换，整个单趟排序完成了。我们写一下代码。
关于这个代码有几个需要注意的地方：
（1）.108行和112行while的第一个循环条件，如果不加的话，我们想象一个数组除了key以外的数都比key大，那么R就会一直向左走甚至越界，所以这个条件是防止越界，即使都比key大，最终也只会走到与L重合的地方就停下来了。
（2）.第二个循环条件为什么带等于号：如果不加等于号，遇到一个与key相等的数，虽然交换了，但right没有--，下次还是会继续交换，造成了死循环。
（3）.等到106行的while循环结束以后，L与R就会相遇，有一个隐含条件，此时相遇对应的那个数一定比key小，为什么呢？因为，当二者相遇的时候无非就两种情况，当L遇R，R在比key小的地方停下来了等着L没找到比key大的过来相遇，当R遇L,相遇位置就是R停的位置，那么一定比key小。
进行这个排序之后，我们发现，key已经走到了left的位置而且把整个数组分为[0,key-1],key,[key+1,n-1](假设数组有n个元素），此时我们需要对key的左右子区间分别再进行一次单趟循环，直到最后区间只剩一个元素，就完成了整个数组的升序排列。但是通过代码我们发现，数组开始的下标通过循环已经找不到了，所以我们需要再创立变量去存储，最后用递归思想去完成排序，这其实与二叉树的前序遍历很像。请看代码：
每一次循环分成了key和左右区间（根与左右子树），而再次单趟后每一个左右区间分别又形成了key和左右区间。
如果我们把key记为数组尾元素的下标，那么就让先让左边先走，满足相遇一定比key大的结论。
快速排序的时间复杂度是n*logn，当情况最坏的时候，复杂度是n^2（当数组有序时）。
以上是霍尔原理的快排，接下来我们看一下前后指针版本的快排。
原理：初始时，prev指针指向序列开头，cur指针指向prev指针的后一个位置，然后判断cur指针指向的数据是否小于key，若小于则prev向后移动一位，并将cur指向的内容与prev指向的内容交换，然后cur++，若大于等于key，则直接cur++，当cur指向尾的时候，再次与key比较，若大于key则cur后移，此时cur越界，将prev指向的内容与key交换。我们用图解释：
初始时，key为6，prev指向6，cur指向1，此时cur小于key，prev后移，cur与prev交换（因为指向同一个地方所以不变），2也是同理，当cur->7时，prev->2，此时直接cur++，prev不动，这样当再遇到cur小于key时，prev就不会与cur重合，即可以看见交换结果了，重复以上步骤，当cur->8时，cur大于key，cur++越界，将prev与key交换，完成单趟排序。这样同样实现了左边比key小，右边比key大，相当于把比key大的依次向右挤。那我们看看代码如何：
我们发现，以上两种快排都是采用了递归思想实现，如果深度太深，递归可能会挂掉。那么有没有非递归的方法呢？答案是yes！
非递归的思想是：把整个数组分成左右区间然后分别压入栈，取出栈顶区间进行单趟排序，右左子区间入栈（当不需要再次分割区间进行排序就不入栈了）。（先入的后排序）因此，我们需要用栈的结构实现。有了思路，我们用代码说话，因为作者还未更新有关栈的结构实现博客（后期更新完数据结构系列大概率会补），所以这里就直接上栈的代码了：
以上是栈的基本结构与功能，下面我们用栈实现一下非递归快排：
注意排序后出入栈的顺序！
至此，我们的快速排序的所有内容就讲解完毕了。
7.归并排序
基本思想：该算法采用分治法，将已有序的子序列合并得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。
先将数组分成子序列，若不符合顺序继续下分，直到符合为止（图中一直分成了每个子序列一个元素），然后再有序排列，合并再排列，也是一种递归的思想。（时间复杂度O(N*logN) )。关于每个数组如何重新排序后合并，我们可以用双指针法，用两个指针分别指向两个序列的第一位，再创建一个临时数组，通过两个指针相比哪个小就把哪个指针对应的值放进临时数组并该指针向后移直到全部排序完成再把临时数组返回即可。（假设要升序排列）
以下是递归思想的代码：
这里有几个细节需要注意，比如i的取值不是0,因为数组分成子序列后不一定是从头开始排序，memcpy拷贝数组的范围不是a，因为有可能把前面已经排好序的地方覆盖成随机值。
我们看看非递归版本。
大致思路：把序列中的每个最小单元都看成有序，然后归并一次进行排序，以此往复，直到全部序列归并排序完毕。我们用gap记录归并每组数据的个数
代码如下：
对代码进行一些解释说明：gap参照上图的归并过程，指每次排序序列中元素个数，我们发现for循环的变量调整部分是j=j+2*gap,即每次归并的序列中元素个数都是上一次的2倍，但我们很容易就发现了问题，如果个数不是2的n次幂怎么办，例如n等于10，此时的end1，begin2，end2就有可能越界，所以我们需要调整一下区间的范围（当越界的时候）于是就有了下面的两个if语句，当begin2越界或者end1越界，此时，我们发现本来需要归并的两个序列因为越界的问题，只需要排序前面的序列即可（因为当end1越界或begin2越界，说明第二个序列是不存在的），而又因为第一个序列是由上一次的归并而来的所以已经有了排序，所以它此时不需要归并，直接跳出循环准备拷贝即可。而当只有end2越界就不一样了，说明第二个序列的元素是有的但个数比第一个序列少，所以我们直接调整它的结尾下标即可。然后再进行每一次的单趟，最后拷贝到a数组去（注意拷贝元素的个数是end2-j+1而不是end2-j）。
至此，我们的归并排序的递归系列和非递归系列就讲解完毕了。
其实我们发现，在上面所有的排序方法中，都是拿出来目标元素去与某一元素比较然后进行位置交换，我们统称为比较排序，其实还有非比较排序，我们接下来详细解释一下。
二、非比较排序（小众且局限）
非比较排序有很多方法，例如计数排序、基数排序、桶排序，因为非比较排序在实际使用中是比较局限且小众的，我们这里就详细展开一种方法讲解。
非比较排序——计数排序
计数排序适合数据范围集中的数组进行排序
原理，统计每个数据出现的次数，假设我们创建一个全为0的数组，如图
（下面一行是下标）
原理就是一个值出现几次，映射的位置次数就++几次，最后统计出次数
假设我们给定数组a={6,1,2,1,9,6}
那么下标为6,1,2,9的地方分别++了2,2,1,1次。到时候再按从小到大的顺序，哪个下标的元素++了几次，就在数组中插几个该数字。
老规矩，上代码。
我们发现，上面的代码和咱们的思路有些不一样，我们来解释一下原因。
在上面的举例，我们数组中的数只有0-9，如果数组中的数是100-109呢？此时我们如果再开辟109个int大小就太浪费空间了。所以，我们可以用每一个数去与其中的最小值作差，差的范围所在区间就在0-9了（也不一定非要是0-9，再大一点也可以），这也就是为什么我们说这个排序只适合数据集中的序列排序。在排序部分中，因为我们得到的是每个数与最小值的差进行插入数组，所以最后我们再需要加一个最小值再插入就是目标数组了。
同时，它的局限性体现在只限于排序整形
三、时间复杂度、空间复杂度、稳定性
什么是稳定性？一对相同的值的相对位置在排序过程中的变化。
1.插入排序
时间O（N^2）,空间O(1), 稳定
2.希尔排序
时间O（N^1.3）,空间O(1),不稳定（相同的数据预排可能分到不同组）
3.选择排序
时间O（N^2）,空间O(1),不稳定
4.堆排序
时间O（N*logN）,空间O(1),不稳定
5.冒泡排序
时间O（N^2）,空间O(1),稳定
6.快速排序
时间O（N^logN）,空间O(logN)(在走递归时需要建立logN层的栈帧）,不稳定
7.归并排序
时间O（N^logN）,空间O(N),稳定
————————
本文结束文章来源：https://www.toymoban.com/news/detail-844554.html
如果对你有帮助的话，请留下你宝贵的三连，关注作者，后续持续更新高质量文章文章来源地址https://www.toymoban.com/news/detail-844554.html
到了这里，关于数据结构——排序方法大全的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[数据结构 -- 手撕排序算法第六篇] 递归实现快速排序（集霍尔版本，挖坑法，前后指针法为一篇的实现方法，很能打）](https://imgs.yssmx.com/Uploads/2024/02/589845-1.png)
