Go Book
07 基本排序算法概述
通过排序（Sorting）可以重新排列一个数据元素集合或序列，目的是排列成一个按数据元素某个项值排序的序列。排序是计算机程序设计中的一种重要操作，作为排序依据的数据项被称为“排序码”，即数据元素的关键码。
为了便于查找，我们很希望计算机中的数据表是按关键码进行有序排列的，例如使用有序表的折半查找会提高查找效率。另外，二叉排序树、B-树和B+树的构造过程也都是一个排序过程。如果关键码是主关键码，则对于任意待排序序列，经排序后会得到一个唯一的结果。如果关键码是次关键码，则可能排序结果会不唯一。造成不唯一的原因是具有相同关键码的数据元素，这些元素在排序结果中，它们之间的位置关系与排序前不能保持一致。
如果使用某个排序方法对任意的数据元素进行序列，例如对它按关键码进行排序，如果相同关键码元素间的位置关系在排序前与排序后保持一致，则这个排序方法是稳定的；如果不能保持一致，则称这种排序方法是不稳定的。
先看排序的过程：
如果有n个记录的序列{R1 ，R2 ，…，Rn }，其相应关键字的序列是{K1 ，K2 ，…，Kn }，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n的一种排列p1 ，p2 ，…，pn ，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1 ≤Kp2 …≤Kpn ，这样就得到一个按关键字有序的记录序列：{Rp1 ，Rp2 ，…，Rpn }。
根据排序时数据所占用存储器的不同，可将排序分为如下两类：
- 内部排序：整个排序过程完全在内存中进行。
- 外部排序：因为待排序记录数据量太大，内存无法容纳全部数据，需要借助外部存储设备才能完成排序工作。
无论是稳定的排序方法还是不稳定的排序方法，都能实现排序功能。在应用排序的某些场合，如选举和比赛等，对排序的稳定性是有特殊要求的。究竟应该怎样证明一种排序方法是稳定的呢？这得从算法本身的步骤中加以证明。证明排序方法是不稳定的，只需给出一个反例说明即可。 在排序过程中，一般进行如下两种基本操作：
- 第一种：比较两个关键字的大小。
- 第二种：将记录从一个位置移动到另一个位置。
其中，第一种操作对于大多数排序方法来说是必要的，而第二种操作则可以通过采用适当的存储方式予以避免。
对于待排序的记录序列，有如下3种常见的存储表示方法：
-
向量结构：将待排序记录存放在一组地址连续的存储单元中。因为在这种存储方式中，存储位置决定了记录之间的次序关系，所以在排序过程中一定要移动记录才能实现。
-
链表结构：采用链表结构时，通过指针来维持记录之间逻辑上的相邻性，这样在排序时，就不需要移动记录元素，只需要修改指针即可。这种排序方式被称为链表排序。
-
记录向量与地址向量结合：将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。这样在排序过程中不需要移动记录本身，只需修改地址向量中记录的“地址”。当排序结束后，按照地址向量中的值来调整记录的存储位置。这种排序方式被称为地址排序。
根据不同的排序思想分为以下几类：
交换类排序法是一种基于交换的排序法，能够通过交换逆序元素进行排序。这种排序思想只需就地比较，一般不需要多余的内存空间。常见的交换类排序有：
在排序时可以有选择地进行，但是不能随便选择，只能选择关键字最小的数据。在选择排序法中，每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到排序完全部记录为止。常见的选择排序方法有：
插入排序非常霸道，它不会考虑别人的感受。插入排序直接在一个已排好序的记录子集基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入完毕为止。例如打扑克牌时的抓牌过程就是插入排序的一个典型例子，每抓一张牌，都需要将这张牌插入到合适的位置，一直到抓完牌为止，可得到一个有序序列。常见的插入排序方法有：
归并排序就是利用归并过程，开始时先将k个数据看成k个长度为1的已排好序的表，将相邻的表成对合并，得到长度为2的（k/2）个有序表，每个表含有2个数据；进一步再将相邻表成对合并，得到长度为4的（k/4）个有序表……如此重复做下去，直到将所有数据均合并到一个长度为k的有序表为止，就完成了排序。
前面所述的各种排序方法使用的基本操作主要是比较与交换，而基数排序则利用分配和收集两种基本操作，基数类排序就是典型的分配类排序。常见的分配类排序方法有：
下面这张图，概况了几种排序算法的特点及时间和空间复杂度：
综合比较各类基本排序算法，有如下建议：
-
简单排序一般只用于n较小的情况。当序列中的记录“基本有序”时，直接插入排序是最佳的排序方法，常与快速排序、归并排序等其他排序方法结合使用。
-
快速排序、堆排序和归并排序的平均时间复杂度均为O(nlogn)，但实验结果表明，就平均时间性能而言，快速排序是所有排序方法中最好的。遗憾的是，快速排序在最坏情况下的时间性能为O(n2 )。堆排序和归并排序的最坏时间复杂度仍为O(nlogn)，当n较大时，归并排序的时间性能优于堆排序，但它所需的辅助空间更多。
-
基数排序的时间复杂度可以写成O(d×n)。因此，它最适用于n值很大而关键字的位数d较小的序列。
-
从排序的稳定性上来看，基数排序是稳定的。除了比较简单的选择排序外，其他各种简单排序法也是稳定的。然而，快速排序、堆排序、希尔排序等时间性能较好的排序方法，以及简单选择排序都是不稳定的。多数情况下，排序是按记录的主关键字进行的，此时不用考虑排序方法的稳定性。如果排序是按记录的次关键字进行的，则应充分考虑排序方法的稳定性。
-
综上所述，每一种排序方法各有特点，没有哪一种方法是绝对最优的。我们应根据具体情况选择合适的排序方法，也可以将多种方法结合起来使用。
接下来我们就要Go语言做以上几种排序算法的描述吧。