我们来介绍几种常见的排序算法并且比较它们的空间，时间复杂度和稳定性
先来定一个标准，不管是什么排序，都先写单趟，再写多趟
1.冒泡排序
冒泡排序是最简单的一种排序算法，在实际的应用中并没有意义，主要的意义就是用来教学的
这里来放一张冒泡排序的图
冒泡排序的基本思路是：前后两个元素进行比较，大的往后走，一趟排完，最大的排到最后，总共只需要排n-1次
代码如下
Swap函数在之后的排序算法中也会反复调用
我们可以通过调试或者打印数组元素来检验是否排序成功了
这里用调试来检验
这是排序之前的数组元素
这是排序之后的
2.插入排序
插入排序的实际意义其实也不大，在之后快速排序的小区间优化可能会用到，但插入排序的效率比冒泡排序高多了，我们等会可以来对比一下
先讲插入排序的基本思路：从第二个元素开始一直到最后一个元素，假设前面的元素都已经有序了，然后将相应元素插入到前面，如果比前面的元素小，那前面的元素往前移，一直到找到比自身小的元素，插入到这个元素的前面
代码如下：
我们可以来对比一下插入排序和冒泡排序的效率
排5w个数据的情况下，插入排序1s都不用，冒泡排序用了6s
3.选择排序
选择排序的一般思路是，从前往后选取最大的一个数，放到最后，依次循环下去就好了
我们这里来用一种更快的方法（其实也快不了多少）
分别选取最大数和最小数放到末尾和开头，然后来进行循环
代码如下
依旧从单层循环开始写，我们这里选择使用下标来控制数组，更方便
一开始先假定最大值和最小值都是初始值，然后从初始值的下一个位置开始判断更新最值
当一次循环结束后，说明找到了最大值和最小值
然后将最小值和最大值放到首尾
再将begin++,end--;
有一个需要注意的点：如果是上面的那种代码，先进行最小值的放置，则需要注意你的首元素是不是最大值，
如果是的话，那么最大值会先跟最小值进行位置的交换，先前最大值位置所储存的值就不是最大值了
所以要进行最大值下标的更新
本质上，这三种排序都是在一个量级的
事实证明，冒泡排序确实没什么实践意义
4.堆排序
堆排序是根据堆这个数据结构完成的，堆是一种完全二叉树，大堆：父亲大于儿子，小堆：父亲小于儿子，堆的逻辑结构上是二叉树，但在物理结构上，堆是用数组来实现的
想要写堆排序，需要前置写一个向下调整的算法，其实向上调整也可以，但是向下调整的效率比较高
如果想要排升序，需要建大堆，如果想要排降序，需要建小堆
建大堆的话，向下调整就需要找到最大的数
向下调整的思路如下：
先假设左孩子比较大，如果右孩子的下标没有越界并且右孩子大于左孩子，那就让chi++，然后再将孩子和父亲进行对比，如果父亲大于孩子，说明父亲就是大的，跳出循环，如果父亲小于孩子，那就交换父亲和孩子的数据，让孩子成为新的父亲
堆排序的思路如下：
先来建大堆，这里来补充一点，可以进行调整的前提是你调整的方向已经是一个堆了，所以我们向下调整从倒数第二行开始调整，相当于最后一个节点的父亲，（n-1）是最后一个数据的下标，（n-1-1）/2就是最后一个节点父亲的下标，然后依次从下往上向下调整，直到i=0。
在建完大堆后，现在下标为0的数据就是整个堆当中最大的数据，我们将其与最后一个元素交换，再从下标为0的位置继续向下调整，找出第二大，第三大，一直循环下去，就排成升序了
堆排序的效率不是前面三种排序算法能比了
我们可以来看一下
在10w这个量级上，堆排序没有一点压力
由于其他排序太慢了，我们让堆排单独来排1000w个数据
可以看到，仅仅花了3s
5.希尔排序
希尔排序是插入排序的变形，从本质上来说，希尔排序是在插入排序之前先进行预排序，以此来提高效率，希尔排序是一种比较抽象的排序，我们得画图来理解一下
我们需要一个变量gap,控制间隔的同时控制组的数量
以这组数据为例，分成了三组，预排序，就是在这gap组内分别进行预排序，排序完之后，再进行总体的插入排序
最里面那层while循环是用来控制单个元素的插入的，倒数第二层循环是来控制哪个元素要进行插入排序的，第二层循环是用来控制哪一组进行插入排序的，第一层循环是用来控制缩小增量的，缩小增量经过先人的推导，现今一般取n/3+1。
希尔排序的时间复杂度是o(n^1.3)
我们来看一下希尔排序的效率，希尔排序的效率跟堆排序是一桌的
6.快速排序（重要，面试里经常考）
快排快排，快速排序就是c语言库中的函数，它的效率不言而喻，以我的理解，快速排序是一个可以不断进化的算法
首先，我们来看一张图
6.1递归写法
6.1.1hoare法
hoare写法的快排的关键是找到一个位置，使得那个位置的数大于等于左边的数，小于等于右边的数，在这里我们需要两个指针来配合寻找
先设置一个left=0，为左指针，再设置一个right=size-1，为右指针，然后设置一个key（一般是第一个元素），然后就开始进行查找，先让右指针找比key指向的位置小的数，再让左指针找比key指向的位置大的数，如果找到了，两个指针位置的元素交换，继续查找（注意：在这个过程中要保证左右指针没有相遇）如果左右指针相遇了，就将key位置的值和相遇位置的值交换
到最后，key就找到了属于它的位置
然后再设置两个区间：[0,right-1]
[right+1,size-1];
再进行重复递归，当左区间大于等于右区间，递归返回
接下来开始实现代码：
这是初始版本的快速排序
在某些特殊情况下，比如第一个数就是最大数或最小数，排序的效率就会大大降低
因此，我们可以从起点，中点，最后，各取一个数，取中间值的数，这样极端情况就比较不容易出现了
接下来来实现一下
快排的本质跟堆排序差不多，而堆排最后一层占总数的一半，倒数第二层占25%，倒数第三层占12.5%，如果能用其他排序，直接将这最后三层排了，效率自然也就提高了
这就叫小区间优化，这里的排序用插入排序是比较合适的
6.1.2双指针法
这种方法需要两个指针来找位置，prev指针指向第一个元素，cur指针指向prev指针的后一个位置，同样需要一个key元素，找位置的规则如下：
1.先判断cur位置的值与key位置的值的大小关系，如果小于，并且cur不在prev的下一个位置，那么就交换prev下一个位置的值和cur位置的值，然后cur++，不管什么情况，cur都需要++
当cur超出数组范围是，交换prev位置的值和key位置的值，接下来来实现代码
同样也可以加上三数取中和小区间优化
6.2非递归写法
有人可能会问，既然已经学了递归的写法，那么为什么还要学非递归呢。
其实递归并不是好事，当递归到一定深度时，可能就会导致栈溢出，因此我们可以利用数据结构栈和循环来达到递归的功能
我们递归的目的是获得左右的区间，既然如此，我们同样可以利用栈来存储左右区间，因为栈的结构导致了它是先进后出的，因此，我们导入区间时，先导入右边界再导入左边界
在确定区间后，我们可以利用之前使用的hoare法或者是双指针法，改编成一个不需要递归的函数，利用循环来达到递归的效果
这里需要注意判断左右区间是否合理
快速排序的时间复杂度是不确定的，最好情况是n*logn，最坏情况是n^2,我们可以来对比一下
可以看到快速排序还是很能打的
7.归并排序
在之前的学习中，我们学习了如何将两个有序链表合并以及合并两个有序数组
归并排序是一种思想上很类似排序算法，假如数组的两个部分都有序，我们就可以使用类似于前面两个问题的思想，将数组的元素有序地插入到新的数组当中，那么，问题来了，怎么使那两个部分有序呢？
我们可以将两个部分分别使用归并排序，到最后每一部分都是单独的一个数字，那么自然就可以视为有序了
具体的过程可以见下图
7.1递归版
通过递归来先使每一个小部分变成有序，再进行该部分的排序
如果区间改成[begin,mid-1][mid,end]则可能会出现bug，导致递归无法停止，造成堆栈
在完成每一趟的递归后，需要把tmp数组中的数据拷贝到原数组，在这里可以使用memcpy这个函数，因为递归的区间并不是从0开始的，所以在拷贝的时候需要将begin加上去，（end-begin+1)就是区间的元素个数
2.非递归版
非递归的归并排序是使用循环来操作的，与递归版相同，同样需要一个tmp数组来储存数据以供拷贝
上述代码中，gap代表的意思是，每组的元素个数，当gap=1时，就代表11归并，当gap=2时，就代表22归并
gap以2倍的速度增长是较为合适的
i控制的是每次归并的起点，当两组归并结束后，i就+=2*gap，跳过归并好的元素，进行下一次归并
[begin1,end1]是第一组元素的区间
[begin2,end2]是第二组元素的区间
因为外层多了一层for循环，我们多定义一个变量j来控制拷贝数组的位置
进行归并的过程与递归版类似，只不过在进行拷贝时要注意拷贝的区间，不能使用begin1，因为begin1在递归的过程有进行改变
上述的代码只能适用于2的倍数的情况，当不是2的倍数时，可
能会出现数组越界的问题
我们将区间打印出来看一下
这几组的数据都有数组越界的情况
可以分为两种情况
情况1：第二组数据的起点就发生越界了，这种情况直接break就好，因为第一组数据已经排好了，不用再进行归并了
情况2：第二组数据的末尾越界，起点没有越界，这种情况需要更改第二组的末尾，将第二组的末尾改为n-1
修正好的代码如下
8.计数排序
这个排序不需要将数字进行比较，本质上是通过下标来进行排序的，有点类似之前的一道字符串的题目
第一个只出现一次的字符_牛客题霸_牛客网
首先，我们需要明确一个事情，计数排序是有局限性的，它只能够排整数
思路：我们先将a数组的元素范围算出来
如上图，假设a数组中的元素是103 101 109 105 106 107 104 102
我们先将count（计数数组）的大小算出来，size=max-min+1.
然后就能够创建计数数组了
这里用calloc申请会比较好，因为会自动将数组里的所有元素都初始化成0，这就是我们需要的
在创建好数组之后，我们就可以来计数了
计数的规则如下：
count[a[i]-min]++;
这样做就可以求出范围中每个数字的个数
计数完后，我们再根据下标从小到大往a数组中插入数据
需要一个新的变量j来控制a数组的位置
具体代码如下
以上就是本篇文章的全部内容了，如果对你有帮助，可以点个赞支持一下，感谢各位的观看
https://gitee.com/mo-ran-qingyun
这是我个人的gitee仓库,账号上文章的代码都会发到仓库里，有兴趣可以看一下
