你知道多少排序算法？

约定不等于承诺〃 2023-07-24 02:44 21阅读 0赞

你知道有哪些排序算法？还记得是怎么实现的吗？今天炒鸡辣鸡就和大家回忆一下有哪些排序算法。

##### 冒泡排序 #####

原理：相邻的2个数进行比较。每次经过一趟比较，最大数或者最小数就会被交换到最后一位。  
时间复杂度：如果是按照从小到大的顺序进行排序，只需要把前n-1个大的数归为到后面的n-1位即可，所以外层循环只需要到len-1。冒泡排序的最坏情况就是把顺序变为逆序，把逆序变为顺序。时间复杂度O（n^2）

##### 选择排序 #####

原理：在要排序的一组数中，选出最小的数与第一个数交换，然后再在剩下的数中选出最小的数与第二个数交换….直到第n-1个数与第n个数比较为止

##### 插入排序 #####

原理：不断向一个已经排好序的数列中按顺序插入数据，最终当最后一个数插入完以后，得到的就是我们需要的有序数列了

##### 希尔排序（插入排序的一种更高效的改进版本） #####

原理：初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率

##### 二分排序 #####

原理：在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left<right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上

##### 快速排序（又称分区交换排序，简称快排） #####

原理：

*  挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）
 *  分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成
 *  递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

##### 归并排序 #####

原理：  
1）划分问题：把序列分成元素个数尽量相等的两半  
2）递归求解：把两半元素分别排序  
3）合并问题：把两个有序表合并成一个。（每次只需要把两个序列的最小元素加以比较，删除其中的较小元素并加入合并后的新表）

##### 基数排序 #####

原理：以整形为例，将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：

（1）分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如６4，个位为４，则放入４号桶中）；

（2）收集，再将放置在0~9号桶中的数据按顺序放到数组中；

（3）重复（1）（2）过程，从个位到最高位（比如32位无符号整型最大数4294967296，最高位为第10位）。基数排序的方式可以采用LSD（Least Significant Digital）或MSD（Most Significant Digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

##### 计数排序 #####

原理：计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

由于篇幅的原因，这里就不罗列详细的实现方案了。我为大家准备了c语言实现版本，欢迎访问 https://blog.csdn.net/xielinrui123/article/details/81506146 查看详情。

知识点我为大家准备了脑图，查看下方图片查看。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpZWxpbnJ1aTEyMw_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpZWxpbnJ1aTEyMw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/ec5a815cb43f493d943bd404ddc50df5.png