Leona+

此文谨献于那段徘徊在AC、WA和TLE之间的时光……

排序，就是把一堆杂乱无章的元素，按照一定的顺序排列起来。比如以前在学校里，考完试老师发考卷的时候，会按照分数从高到低来发，于是他就需要事先把考卷按顺序排好，然后在上课的时候发掉。把考卷按分数从高到低排好的过程，就可以称为排序。

排序的方法有很多种，有一些在日常生活中可以用得到，另一些则是仅用于计算机领域，因为计算机的思考过程和人类多少有点不一样。

从一个简单的例子开始：扑克的“争上游”玩法，假设没有顺子和葫芦（即三拖一或三拖二）的规则，所以手中的牌按照牌面的大小来排序是比较合理的。发牌完成之后，我一般会一张一张地摸起面前的牌，每摸起一张牌，就把它插入手中牌的相应位置，并保证手中的牌有序。比方说，摸起第二张的时候，如果它比第一张大，就放在第一张的后面，否则就放在第一张的前面；摸起第三张的时候，就按大小放在第一张之前、第一第二张之前或者第二张之后；以此类推。这样把面前的牌都拿到手中时，手中的牌就是有序的。这种方法被称为插入排序(Insertion Sort)。（插入排序有一个进化版叫做希尔排序(Shell Sort)，有兴趣的同学可以自已研究。）当然也有些人不喜欢这种方法，他们一下子把所有的牌都拿起来，这时候手里的牌是无序的，然后他们会做一个操作：（假设一共有12张牌），先在所有的牌中挑出牌面最大的一张，比如黑桃2，放在所有牌的最后面，然后在剩于的11张牌中，挑出最大的一张，比如红桃A，放在黑桃2之前，以此类推，也可以把牌都理好顺序。这种方法叫做选择排序(Selection Sort)。

而在“八十分”的玩法中，上述两种排序方法就不怎么适用了。按照八十分的规则，手中的牌通常是按照花色来摆放的，先把同花色的牌放在一起，然后再对四种花色，分别调整同花色牌的顺序（假设是需要有顺序的）。这种方法叫做桶排序(Bucket Sort)，或者基数排序(Radix Sort)。每种花色可以视为一个桶，先把牌按照它的花色分别扔进这四个桶里，然后再对每个桶中的牌分别进行排序。桶排序在一定条件下可以进化成计数排序(Counting Sort)，这里不多说了。

桶排序和前面的插入排序、选择排序有一点不一样。在桶排序中，所有的元素都被放到相应的桶里之后，每个桶里的排序方式，可以是不一样的。比如第一个桶中使用插入排序，第二个桶继续使用桶排序。从另一个角度来说，各个桶之间是相互独立的，排序操作可以同时进行。也就是说，如果扑克牌的数量很多，可以先把牌放进桶里，然后找多个人，每个人对一个桶进行排序，这样的并行操作可能提高效率。而在插入排序或者选择排序中，想要并行操作就相关来说复杂一点。

另一种可以进行并行操作的方法是合并排序(Merge Sort)，与桶排序不同的是，合并排序先把要排序的扑克牌分成几份，每份都是没排过序的，然后分别对每一份进行排序，于是每一份内部都是有序的了（假设顺序是从小到大），最后要做的操作是，比较每一份扑克牌的第一张，选出最小的一张牌，由于每一份牌都是从小到大有序的，所以选出来的那一张一定是所有牌中最小的，把这张放到一边，再重复同样的操作选出一张最小的牌，放在刚才那张牌的上面，以此类推，就可以达到排序的效果了。不难想象，对每一份扑克牌的排序操作，是可以同时进行的。

以上几种排序方法是日常中能见到的，下面来说说仅用于计算机中的排序方法。

首先，也就是最基本的就是冒泡排序(Bubble Sort)了。对于一个长度为n的数组A，从i=0到n-2，比较A[i]和A[i+1]，如果A[i]>A[i+1]，则把它们交换，这样一次循环下来，A[n-1]就是数组中最大的数（证明略:P），然后重复n次，就可以把整个数组排序了。顺便复习一下算法复杂度，冒泡排序的时间复杂度是O(n²)，空间复杂度为O(1)。

剩下最著名的快速排序(Quicksort)了，顾名思义，它是目前公认最快的内排序算法。（插一句，内排序是指所有需要排序的元素都存放在内存中，如果内存不足以存放所有的元素，由于外部存储器速度的制约，排序算法需要进行一定的调整。）快排的基本思想是，先在数组中取一个元素x，然后整理这个数组，使x左边的元素都不大于x，而x右边的元素都不小于x，然后再对x左右两边分别应用快排算法，最终将整个数组排序。不难发现，快排算法的好坏取决于元素x的选取，如果每次都很不巧得选了最小的元素，快排对退化成选择排序。一般来说，快排的时间复杂度为O(nlg(n))，空间复杂度是O(lg(n))。和合并排序一样，快排是分治思想一个典型定用，也就是说，它可以使用并行算法优化。

以上几种就是基础的排序方法了，还有一些由它们演化、改进出来的算法，就不多提了。

顺便复习一下复杂度，在单线程情况下，理论上最快的是桶排序（或者计数排序），可以达到O(n)，但是需要使用大量的空间。一般情况下最快的是快速排序，O(nlg(n))时间，O(lg(n))空间。其它被快排BS掉的方法，多数是O(n²)时间，O(1)空间。