3.5. 基础排序算法¶
排序算法是学习算法的必修内容，是算法这个学科领域中最为重要的内容之一。
排序算法对一个元素序列按照一定的顺序规则进行排序，一般是指按升序排序，即从小到大的排。虽然学习排序算法时总是用整数序列提供示例，但实际上排序的元素序列并不限于整数，也不限于数，而是任何类型的元素，只要它可以按一种确定的规则相互比较大小即可。这在前面3.4.5“二分法基础及二分查找“这一节中已经讲过，叫做“序关系”。比如元素可以是字符串，按照字典序来进行排序。也可以是任何自定义的数据类型，通常是一些struct结构类型，只要为它实现了小于等六种比较运算就可以用来排序（事实上C++模板算法库提供的排序函数可以对任何自定义数据类型进行排序，只需要实现一个小于运算即可）。
排序算法也是计算机科学家和软件工程师们研究得最多最彻底的一个算法门类。目前常见的排序算法有许多种，按不同的分类方式可以分成以下几类：
一、按排序的实现技术分，可以分为基于元素比较的排序和不基于元素比较的排序两类。基于元素比较的排序算法是最常见的，也是通用型的排序算法，可以适用各种不同数据类型；不基于元素比较的排序算法往往是一些针对特定数据类型开发设计的特殊排序算法，例如基数排序基本上就只能对整数进行排序。
冒泡排序、希尔排序、选择排序、插入排序、快速排序、归并排序、二叉树排序、堆排序，这些经典的排序算法都是基于元素比较的排序，是尤为重要的一类排序算法。基于元素比较的排序算法能达到的最快效率是 \(O(n\log n)\) 时间。
桶排序、计数排序、基数排序等是不基于元素比较的排序算法，在某些特定场景下，它们往往能发挥特别的作用，速度可能会非常之快。
二、按排序的稳定性分，可以分为稳定排序和不稳定排序。
稳定性，是指当被排序的序列中有等值元素存在时，排序前和排序后这些等值元素的相对顺序是否发生改变。排序后等值元素还能保持在原序列中的相对位置的，就称为稳定排序；若无法确保原相对位置的则称不稳定排序。
例如原序列为 [5,1,3,1,2]，这里有两个1，一个在前一个在后，如果排序之后，原先前面那个1还是排在后面那个1的前面，就是稳定排序。如果这个相对顺序不能确保就是不稳定排序。对于纯数字的排序来说，讲究稳定性似乎有点多此一举，但是对于某些自定义数据类型来说，却是非常重要的。举例来说，比如有这样一台服务器，它用一个任务池在后台接收来自客户端的任务请求。每一个任务都有一个优先级，从0到9，0级表示最优先的任务，9级是最不优先的任务。任务池只是单纯地按照任务接收的时间顺序存放所有任务。当任务池满了的时候，它会通知服务器启动一次任务调度，把池中积累的任务按照优先级从0到9的顺序分发给服务器进行处理。所以任务调度软件需要对池中所有任务按优先级排序，但是对于同一优先级的多个任务还要保持先来后到的顺序，接收时间靠前的任务要先被调度，即要保持池中原相对顺序不变。这个任务调度就需要用一个稳定的排序算法了。
三、按关键字的多少来分，可以分为单关键字排序和多关键字排序。
关键字就是用来确定元素顺序的那个值。比如对一个整数序列进行排序，每一个元素就是一个整数，也就只有这一个值，这种就叫做单关键字排序。又比如说对一个班级的学生期末考试成绩单按学号排序，那么虽然每个元素有多个值（学号、姓名、语文成绩、数学成绩、英语成绩、科学成绩、总分等等），但是我们只是按照学号来进行排序，排序关键字就是学号这个整数值，这也是单关键字排序。如果我们要按这样的规则排序：首先按照总分排序，总分相同的学生按照学号排序，那么排序的关键字就有两个，总分和学号。总分称为主关键字，学号称为次关键字或第2关键字。如果有更多个关键字，那么依次称为第3关键字、第4关键字……
四、按是否将要排序的数据全部读入内存中进行排序来分，可以分为内排序和外排序。
内排序就是把所有数据全部读入内存，然后在内存中完成排序的排序算法。外排序则是读一部分数据进入内存，另一部分保持在硬盘等外存储器中，一边读一边排并且一边写到外存储器去，最终排完序的结果也写入到硬盘文件等外存储器中的排序算法。外排序一般用于数据量特别大，无法全部读入内存的场景，比如存储于海量存储器上的大型数据库系统，往往要对数个T甚至几十T上百T的数据进行排序，这就完全无法把数据全部读入内存中来进行排序。
由于硬盘等外存储器和内存之间存在巨大的读写速度差距，而且外排序不能一次性完成排序，总要进行多次读写，所以外排序的速度会比内排序慢许多。目前算法竞赛基本不会涉及外排序算法，所以初期我们也不打算介绍外排序。但是随着现在大数据技术的强势崛起，外排序算法在实际应用中的价值越来越大，对外排序的研究也越来越深入，成果越来越丰富，今后可能会是排序算法研究的一个重要方向。
五、按是否破坏原序列来分，可以分为排序和索引。
排序就是通常所说的排序算法，排序算法执行完毕后，原来的序列会被破坏，元素都按新的顺序重新摆放了。索引算法则不破坏原数据序列，而是另外新建一张索引表，在索引表中按顺序存放元素在原序列中的位置编号。
例如对整数序列 [2, 4, 3, 1] 进行索引后，会生成这样一张索引表：[4, 1, 3, 2]，表示第1个元素是原序列中的第4个元素1，第2个元素是原序列中的第1个元素2，第3个元素是原序列的第3个元素3，第4个元素是原序列的第2个元素4。
索引算法在大型数据库系统中非常重要。大型数据库系统中往往存放着大量的数据表，表里的数据量非常巨大，可能有几千万甚至上亿行，每一行有成百上千列，数据的排序关键字可能有几十个之多。如果对这张表进行排序，又只能使用速度较慢的外排序。当增加新记录的时候又要重新进行排序。这样就会严重影响数据库的性能。所以大型数据库的设计者一般不会对数据表进行排序，而是用建立索引的方式来确保数据的有序性。
索引虽然严格上来说和排序是两码事，但是二者有天然的联系。对于数据量特别巨大，关键字特别多的场景，索引能提供更大的灵活性和更强的性能。
对排序算法的评价，主要有四个指标：平均时间复杂度、最好时间复杂度、最坏时间复杂度和空间复杂度。根据问题的要求不同，还要选择采用稳定排序还是不稳定排序。一般来说，稳定排序的平均速度要比不稳定排序慢一些，如果问题对稳定性没有要求那一般就选用不稳定的排序算法。
注解
基于元素比较的排序算法，在衡量其时间复杂度时都采用元素比较运算作为基本运算。
有些排序算法需要用到复杂的数据结构，例如二叉树排序要用到平衡二叉树，性能要求很高的时候要用到红黑树，多关键字索引算法要用到B+树，堆排序要用到堆结构。而有些排序算法只是基于最通常的顺序存储结构，使用数组就可以完成排序。本部分我们只基于数组进行排序算法介绍，要用到更高级的数据结构的排序算法留到相应的数据结构学完之后再介绍。
在本部分，我们将学习五种基础的基于元素比较的排序算法：冒泡排序、选择排序、插入排序、归并排序和快速排序（后三种是重点），三种非比较型排序算法：桶排序和计数排序和基数排序，学习 algorithm 库中排序类库函数的使用，并学会怎样让自定义的struct支持比较运算。我们还将学到一些和排序相关的实用技巧，比如一些常见的多关键字排序，一种简单的索引算法，三种寻找k位数（即原序列中第k小的元素）的算法。