常见经典排序算法总结

谁借莪１个温暖的怀抱￠ 2022-11-21 03:40 191阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
算法几乎是每个软件从业者都会或多或少需要接触的内容，而排序则是算法中最基础的内容，这篇文章整理了常见的经典排序算法，并对于算法的实现和要点进行整理。

### 目录 ###

*  经典排序之冒泡排序
 *  经典排序之选择排序
 *  经典排序之插入排序
 *  经典排序之希尔排序
 *  经典排序之计数排序
 *  经典排序之归并排序
 *  经典排序之快速排序
 *  总结

--------------------

# 经典排序之冒泡排序 #

冒泡排序顾名思义，升序排序的时候小的元素像气泡一样一个一个的浮上去，对于N个元素，通过两层循环来完成排序，外层循环N-1次，下标用来记录已排序的元素的位置，升序的要求下每次获取当次排序中的最小值，并将其排在已排序的最后一个。内层循环使用临位相比的方法来确定是否需要进行交换，在内层循环中保证外层循环的当前下标中保存的是当前剩余元素中的最小元素。

> 详细的实现与要点解析可参看如下内容：
> 
>  *  [https://liumiaocn.blog.csdn.net/article/details/109278050][https_liumiaocn.blog.csdn.net_article_details_109278050]

--------------------

# 经典排序之选择排序 #

选择排序和冒泡排序非常相像，都是使用比较和交换作为排序的重要手段，每次外层循环得到一个未排序的最小值，将序列分为已排序和未排序两种。但区别也非常清晰，冒泡排序的交换在内层循环进行，选择排序的交换在外层进行，内层循环只需要获取当次循环最小元素的下标。

> 详细的实现与要点解析可参看如下内容：
> 
>  *  [https://liumiaocn.blog.csdn.net/article/details/109282416][https_liumiaocn.blog.csdn.net_article_details_109282416]

--------------------

# 经典排序之插入排序 #

插入排序在理解上可以参考打牌时的同花顺的单手排序过程，插入只是算法的一个重要动作，另外还有一个动作就是选择，如果将插入排序理解为元素从1到N的一个初始化过程，每次插入之后保证当前的序列是已排序的也没有问题，但是这种情况需要而外的一个O（n）的空间，相较于冒泡排序和选择排序的交换，插入排序的特点在于后移和插入。首先将外层循环的当前元素保存在一个额外的变量之中，内层循环显著的特点是在已排序的序列中进行循环，根据要插入的元素和已排序的元素进行比较，决定移位。然后在外层循环中进行插入。

> 详细的实现与要点解析可参看如下内容：
> 
>  *  [https://liumiaocn.blog.csdn.net/article/details/109282416][https_liumiaocn.blog.csdn.net_article_details_109282416]

--------------------

# 经典排序之希尔排序 #

希尔排序是在插入排序的基础上进行的，增量递减的插入排序改进是希尔算法的核心内容，增量在算法中被称为增量，比如一个待排序列有10个元素，增量递减的思路可以进行自行定制，比如除2，首次增量为10/2=5，然后接下来为5/2=2，然后2/2=1，所以称为增量递减。

> 详细的实现与要点解析可参看如下内容：
> 
>  *  [https://liumiaocn.blog.csdn.net/article/details/109331619][https_liumiaocn.blog.csdn.net_article_details_109331619]

--------------------

# 经典排序之计数排序 #

计数排序在理解上大概是比冒泡排序还要简单的排序，它的做法就是根据待排序的内容生成一大块连续的空间，能够保存待排序的最大值-最小值的范围，然后巧妙的将值作为下标进行保存，而该下标的元素中保持记录重复的次数，然后输出的时候根据顺序进行输出，有计数值的按照计数值进行输出即可，有重复的根据计数值进行递减。虽然此排序有时被成为桶排序或者箱排序，虽然可以将其理解为桶的个数最大情况下的个例，但是多少还是有些不同。

> 详细的实现与要点解析可参看如下内容：
> 
>  *  [https://liumiaocn.blog.csdn.net/article/details/109302972][https_liumiaocn.blog.csdn.net_article_details_109302972]

--------------------

# 经典排序之归并排序 #

归并排序在理解上的那点复杂性主要在于其递归方式的分而治之的拆分与合并。归并在汉语中本身就含有合并的意义，实际上更准确的说，应该是拆分合并算法，拆分至单个元素，这样最小力度都是有序的，然后递归的合并就可以在有序的基础上进行了，而有序状况下的合并复杂度是很容易可以做到O(n)的，由于分层是可以达到对数级的效率，所以整体的复杂度为O(nlogn)。

> 详细的实现与要点解析可参看如下内容：
> 
>  *  [https://liumiaocn.blog.csdn.net/article/details/109288438][https_liumiaocn.blog.csdn.net_article_details_109288438]

--------------------

# 经典排序之快速排序 #

快速排序乍一看很像归并排序，但实际上这是由于两者都是使用了分而治之的思路，所以在算法上都有递归的实现。但是仔细看来二者还是有很多区别的。快速排序的核心在于分区算法，分区算法设定基准值，根据基准值将数据分为三部分：左侧小于基准值序列、基准值、右侧大于基准值的序列。层层递归即完成整体快排。

> 详细的实现与要点解析可参看如下内容：
> 
>  *  [https://liumiaocn.blog.csdn.net/article/details/109289285][https_liumiaocn.blog.csdn.net_article_details_109289285]

--------------------

# 总结 #

包括快排在内的经典排序算法的实现都非常简单，如果写的简洁一些的情况下，核心排序代码往往只需数行，还是值得认真学习和总结一下的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/2486db67605e4f3ba735d717f5d66a6c.png
[https_liumiaocn.blog.csdn.net_article_details_109278050]: https://liumiaocn.blog.csdn.net/article/details/109278050
[https_liumiaocn.blog.csdn.net_article_details_109282416]: https://liumiaocn.blog.csdn.net/article/details/109282416
[https_liumiaocn.blog.csdn.net_article_details_109331619]: https://liumiaocn.blog.csdn.net/article/details/109331619
[https_liumiaocn.blog.csdn.net_article_details_109302972]: https://liumiaocn.blog.csdn.net/article/details/109302972
[https_liumiaocn.blog.csdn.net_article_details_109288438]: https://liumiaocn.blog.csdn.net/article/details/109288438
[https_liumiaocn.blog.csdn.net_article_details_109289285]: https://liumiaocn.blog.csdn.net/article/details/109289285