本文共 3147 字，大约阅读时间需要 10 分钟。

排序算法

排序是数据处理中经常使用的一种重要运算。如何利用计算机进行排序，特别是高效地进行排序是计算机应用中的重要课题之一。因为其使用较广泛，所以排序算法在很多领域得到相当地重视。所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

排序算法的分类

从计算机诞生至今，不少计算机科学家、数学家发明了各式各样的排序算法，各种排序算法可以按照不同原则加以分类。

• 内部排序
  在排序过程中，整个文件都是放在内存中处理，排序时不涉及数据的内存与外存交换。
• 外部排序
  在排序过程中，文件中的数据需要进行内存与外存间的交换。

内部排序适用于记录个数不是特别庞大的文件，外部排序则适用于记录个数很庞大，无法将文件中的全部记录一次放入内存的大文件。

内部排序涉及很多比较基础和经典的排序算法，所以我们常拿内部排序讨论和学习，内部排序按所用策略不同可以分为五大类：

• 插入排序：将关键字插入到有序区的合适位置。
• 交换排序：通过交换将关键字换到有序区间。
• 选择排序：选出文件最大（小）关键字放入有序区。
• 归并排序：将两个或多个文件合并为一个有序文件。
• 分配排序：将关键字分配到指定位置。

我们常说的八大排序（也有说九个、十个的，因为有几个算法虽也很经典，提到排序时也拿出来讨论，但现在使用的相对较少）都是属于这五类。

标 * 的就是日常使用较少的，但有时也拿出来一起分析的排序算法。

排序算法的详解

直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序、二路归并排序、基数排序就是所说的八大排序。这八个算法非常经典且使用较多，我将每个排序算法的具体排序过程另写了文章，有超详细的图文解析，细化到每一步的排序操作，并附上了参考代码（C语言）。链接如下

✍

✍ ✍ ✍ ✍ ✍ ✍ ✍

排序算法的性能

算法分析时，评价一个算法的性能主要包括三个方面：

①执行算法所耗费的时间——时间复杂度 ②执行算法所耗费的空间——空间复杂度 ③算法应易于理解、易于编写、易于调试 （若对时间复杂度和空间复杂度的概念不太了解可查看此文章 ）

对于排序算法，除了要分析其时间复杂度、空间复杂度和理解编写的难易度之外，还有一个指标，就是稳定性。排序的稳定性是指排序前后数值相等的关键字的相对位置是否发生变化，若无变化则是稳定的，否则是不稳定的。

排序算法	最优时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	难易性
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	易
希尔排序	$O(n)$	$O(n$1.3$)$	$O(n^2)$	$O(1)$	不稳定	难
起泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	易
快速排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(n^2)$	$O(lo{g}_{2}n)$~$O(n)$	不稳定	难
直接选择排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	易
堆排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(1)$	不稳定	难
二路归并排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(n)$	稳定	难
基数排序	$O(d\ast (n+k))$	$O(d\ast (n+k))$	$O(d\ast (n+k))$	$O(n+k)$	稳定	难

迄今为止，已有的排序算法远不止以上这几种，人们之所以热衷于研究排序算法，不仅是由于排序在计算机中所处的重要地位，还因为不同的算法各有其优缺点，很难有一种排序算法适用于所有场合，在不同的情境下需选择不同的排序算法才能更好的使运算效率得到提升。

（1）待排序记录较少（如n<50）

对于记录较少时，直接插入排序、起泡排序、直接选择排序这三个算法优先考虑，以为n较小时，算法执行的时间差异很小，而这几种算法简单基础易于理解和编写，能基本满足需求，所以对于少数记录排序没必要花费时间去写较复杂的算法。在这三个算法中，如果待排序记录已基本有序，并且希望排序稳定，则选用直接插入排序和起泡排序为宜；若待排序记录偏多一些，不需考虑稳定性，则直接选择排序更好一些，因为这三个算法时间复杂度虽然都是同一数量级，但看其具体排序过程，直接选择排序的交换次数要略微少于其他两种。希尔排序虽比这三个稍难理解，但相比于剩下的还算简单，它是对直接选择排序的优化，整体性能优于直接插入排序，但是不稳定。

（2）待排序记录较多

这些排序算法中除了基数排序是分配式排序，其余都是基于比较的排序方法，在基于比较的这些排序算法中，至少需要的时间是$O(nlo{g}_{2}n)$，待排序记录较多时，应采用时间复杂度较低的排序算法：快速排序、堆排序、归并排序。快速排序被认为是目前基于比较的内部排序中最优的方法，当待排序关键字随机分布时快速排序平均时间最短；而堆排序比快速排序节省空间，并且快速排序可能出现最坏情况的时间复杂度，堆排序则不会，但二者皆是不稳定的排序算法；若要求稳定的排序，则可选择归并排序。基数排序不依赖于关键字的比较，而是利用分解关键字进行分配达到排序目的，是一种牺牲空间来换取时间的方法，基数排序一般不存在最坏情况，是可能在$O(n)$时间内完成排序的算法，并且是稳定的。基数排序的优点很亮眼，时间短且稳定，但其缺点也很明显，就是它只适用于字符串、整数这类有明显结构特征的关键字，当排序记录取值范围是无穷集合，且无法分解，这时基于分配的基数排序就很难实施。

排序算法的选择

总结

排序算法是在编程和算法学习中的基础和重点，也算是对算法认识的启蒙，让我们开始用计算机的方式去思考了一个日常生活中常见的问题，学习编程我们就应该适应这种计算机的思维。排序算法的种类很多，方式方法也很多样，在合适的情景下，选择合适的算法，解决合适的题目是最关键的。

写在最后

参考资料:

《数据结构-用C语言描述》高等教育出版社 《计算机算法设计与分析》电子工业出版社 相关排序算法-百度百科

（只是分享个人学习时的想法和理解，如有问题还望大佬指点）

转载地址：http://ygmxi.baihongyu.com/