我们来介绍几种常见的排序算法并且比较它们的空间时间复杂度和稳定性先来定一个标准不管是什么排序都先写单趟再写多趟1.冒泡排序冒泡排序是最简单的一种排序算法在实际的应用中并没有意义主要的意义就是用来教学的这里来放一张冒泡排序的图冒泡排序的基本思路是前后两个元素进行比较大的往后走一趟排完最大的排到最后总共只需要排n-1次代码如下Swap函数在之后的排序算法中也会反复调用我们可以通过调试或者打印数组元素来检验是否排序成功了这里用调试来检验这是排序之前的数组元素这是排序之后的2.插入排序插入排序的实际意义其实也不大在之后快速排序的小区间优化可能会用到但插入排序的效率比冒泡排序高多了我们等会可以来对比一下先讲插入排序的基本思路从第二个元素开始一直到最后一个元素假设前面的元素都已经有序了然后将相应元素插入到前面如果比前面的元素小那前面的元素往前移一直到找到比自身小的元素插入到这个元素的前面代码如下我们可以来对比一下插入排序和冒泡排序的效率排5w个数据的情况下插入排序1s都不用冒泡排序用了6s3.选择排序选择排序的一般思路是从前往后选取最大的一个数放到最后依次循环下去就好了我们这里来用一种更快的方法其实也快不了多少分别选取最大数和最小数放到末尾和开头然后来进行循环代码如下依旧从单层循环开始写我们这里选择使用下标来控制数组更方便一开始先假定最大值和最小值都是初始值然后从初始值的下一个位置开始判断更新最值当一次循环结束后说明找到了最大值和最小值然后将最小值和最大值放到首尾再将begin,end--;有一个需要注意的点如果是上面的那种代码先进行最小值的放置则需要注意你的首元素是不是最大值如果是的话那么最大值会先跟最小值进行位置的交换先前最大值位置所储存的值就不是最大值了所以要进行最大值下标的更新本质上这三种排序都是在一个量级的事实证明冒泡排序确实没什么实践意义4.堆排序堆排序是根据堆这个数据结构完成的堆是一种完全二叉树大堆父亲大于儿子小堆父亲小于儿子堆的逻辑结构上是二叉树但在物理结构上堆是用数组来实现的想要写堆排序需要前置写一个向下调整的算法其实向上调整也可以但是向下调整的效率比较高如果想要排升序需要建大堆如果想要排降序需要建小堆建大堆的话向下调整就需要找到最大的数向下调整的思路如下先假设左孩子比较大如果右孩子的下标没有越界并且右孩子大于左孩子那就让chi然后再将孩子和父亲进行对比如果父亲大于孩子说明父亲就是大的跳出循环如果父亲小于孩子那就交换父亲和孩子的数据让孩子成为新的父亲堆排序的思路如下先来建大堆这里来补充一点可以进行调整的前提是你调整的方向已经是一个堆了所以我们向下调整从倒数第二行开始调整相当于最后一个节点的父亲n-1是最后一个数据的下标n-1-1/2就是最后一个节点父亲的下标然后依次从下往上向下调整直到i0。在建完大堆后现在下标为0的数据就是整个堆当中最大的数据我们将其与最后一个元素交换再从下标为0的位置继续向下调整找出第二大第三大一直循环下去就排成升序了堆排序的效率不是前面三种排序算法能比了我们可以来看一下在10w这个量级上堆排序没有一点压力由于其他排序太慢了我们让堆排单独来排1000w个数据可以看到仅仅花了3s5.希尔排序希尔排序是插入排序的变形从本质上来说希尔排序是在插入排序之前先进行预排序以此来提高效率希尔排序是一种比较抽象的排序我们得画图来理解一下我们需要一个变量gap,控制间隔的同时控制组的数量以这组数据为例分成了三组预排序就是在这gap组内分别进行预排序排序完之后再进行总体的插入排序最里面那层while循环是用来控制单个元素的插入的倒数第二层循环是来控制哪个元素要进行插入排序的第二层循环是用来控制哪一组进行插入排序的第一层循环是用来控制缩小增量的缩小增量经过先人的推导现今一般取n/31。希尔排序的时间复杂度是o(n^1.3)我们来看一下希尔排序的效率希尔排序的效率跟堆排序是一桌的6.快速排序重要面试里经常考快排快排快速排序就是c语言库中的函数它的效率不言而喻以我的理解快速排序是一个可以不断进化的算法首先我们来看一张图6.1递归写法6.1.1hoare法hoare写法的快排的关键是找到一个位置使得那个位置的数大于等于左边的数小于等于右边的数在这里我们需要两个指针来配合寻找先设置一个left0为左指针再设置一个rightsize-1为右指针然后设置一个key一般是第一个元素然后就开始进行查找先让右指针找比key指向的位置小的数再让左指针找比key指向的位置大的数如果找到了两个指针位置的元素交换继续查找注意在这个过程中要保证左右指针没有相遇如果左右指针相遇了就将key位置的值和相遇位置的值交换到最后key就找到了属于它的位置然后再设置两个区间[0,right-1][right1,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-begin1)就是区间的元素个数2.非递归版非递归的归并排序是使用循环来操作的与递归版相同同样需要一个tmp数组来储存数据以供拷贝上述代码中gap代表的意思是每组的元素个数当gap1时就代表11归并当gap2时就代表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计数数组的大小算出来sizemax-min1.然后就能够创建计数数组了这里用calloc申请会比较好因为会自动将数组里的所有元素都初始化成0这就是我们需要的在创建好数组之后我们就可以来计数了计数的规则如下count[a[i]-min];这样做就可以求出范围中每个数字的个数计数完后我们再根据下标从小到大往a数组中插入数据需要一个新的变量j来控制a数组的位置具体代码如下以上就是本篇文章的全部内容了如果对你有帮助可以点个赞支持一下感谢各位的观看https://gitee.com/mo-ran-qingyun这是我个人的gitee仓库,账号上文章的代码都会发到仓库里有兴趣可以看一下