写在前面
我们先提出几个问题.
Problem 1.1
试用最快的方法找到给定五个两两不同的数的中位数.
Problem 2.1
试求基于比较的排序的时间复杂度的下确界.
Problem 3.1
现在有一个序列, 其只包含0, 1, 2三种元素. 那么, 在只允许额外申请常数空间的前提下, 试求最快的对这个序列排序的方法.
对Problem 1.1的思考有助于我们引入比较, 排列, 和排序的概念. 对于Problem 2.1来说, 我们将一般性地探讨一下基于比较的排序的原理和复杂度分析, 从而在得出结论的同时给出详细的说明.
我们将在本文的最后部分解决Problem 3.1这一个特殊的排序问题. 在此基础上, 我们将探讨一下不基于比较的排序的原理和复杂度分析, 以及适用范围.
Problem 1.1
试用最快的方法找到给定五个两两不同的数的中位数.
Problem 2.1
试求基于比较的排序的时间复杂度的下确界.
Problem 3.1
现在有一个序列, 其只包含0, 1, 2三种元素. 那么, 在只允许额外申请常数空间的前提下, 试求最快的对这个序列排序的方法.
对Problem 1.1的思考有助于我们引入比较, 排列, 和排序的概念. 对于Problem 2.1来说, 我们将一般性地探讨一下基于比较的排序的原理和复杂度分析, 从而在得出结论的同时给出详细的说明.
我们将在本文的最后部分解决Problem 3.1这一个特殊的排序问题. 在此基础上, 我们将探讨一下不基于比较的排序的原理和复杂度分析, 以及适用范围.
复杂度(Complexity)
每当我们探讨一个算法时, 一个问题将会被自然而然地提及. 那就是, 给定输入数据, 这个算法会在多快的时间内运行完毕? 这个算法又会占用多少空间? 对算法需求的时间和空间资源的分析, 通称为复杂性分析(complexity analysis). 由于空间的复杂性分析相对时间较为简单, 所以在下文中我们以时间复杂性分析为例.
在计算理论中, 常数次的计算操作, 甚至常数倍的操作时间都会被认为是较为次要的因素, 而最重要的则是这个总计算次数/时间, 定义为T, 相对于输入数据的规模, 定义为n, 的函数的阶. 即, 我们更加关心这个函数是一个线性的, 平方级的, 指数级的, 或是对数级的, 等等.
这个原因不难解释. 当n不断膨胀时, 函数的阶往往成为运算次数/时间的最主要因素, 可以被认为是体现了这个函数的增长率. 我们把这个"增长率"定义为函数的时间复杂度(time complexity), 严格定义如下.
在计算理论中, 常数次的计算操作, 甚至常数倍的操作时间都会被认为是较为次要的因素, 而最重要的则是这个总计算次数/时间, 定义为T, 相对于输入数据的规模, 定义为n, 的函数的阶. 即, 我们更加关心这个函数是一个线性的, 平方级的, 指数级的, 或是对数级的, 等等.
这个原因不难解释. 当n不断膨胀时, 函数的阶往往成为运算次数/时间的最主要因素, 可以被认为是体现了这个函数的增长率. 我们把这个"增长率"定义为函数的时间复杂度(time complexity), 严格定义如下.
$$ f(n) = O(g(n)) \iff \exists c>0, n_0>0, s.t. f(n) \leq cg(n), \forall n \geq n_0. \ \\ f(n) = \Theta(g(n)) \iff \exists c>0, n_0>0, s.t. f(n) \geq cg(n), \forall n \geq n_0. \ \\ f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) = \Omega(g(n)) $$
这个定义比较抽象, 叙述起来就是: 如果函数f(n)在n充分大的时候, 存在一个常数, 使得f(n)小于g(n)的常数倍, 则称f(n) = O(g(n)). 这样的话, g(n)就确定了f(n)的上界, 所以我们可以用O(g(n))来代表f(n). 通常我们选取比较简单的函数来作为代表, 比如O(n), O(log(n)), O(n^2)等等.
类似地, 我们可以定义下界Ω和确界Θ. 对于算法而言, 我们更关心的是其时间的函数上界, 所以O和Θ更为常用一些.
举一个简单的例子. 如果把一个长度为n的序列从头到尾遍历一遍, 那么其时间复杂度是O(n). 遍历两遍, 三遍也并不改变这个复杂度. 但如果遍历次数是n的一个函数的话, 比如遍历了n遍的话, 那么其时间复杂度就是O(n^2)了.
类似地, 我们可以定义下界Ω和确界Θ. 对于算法而言, 我们更关心的是其时间的函数上界, 所以O和Θ更为常用一些.
举一个简单的例子. 如果把一个长度为n的序列从头到尾遍历一遍, 那么其时间复杂度是O(n). 遍历两遍, 三遍也并不改变这个复杂度. 但如果遍历次数是n的一个函数的话, 比如遍历了n遍的话, 那么其时间复杂度就是O(n^2)了.
比较与排列(Comparing & Permutation)
我们现在引入排序这个概念. 先思考Problem 1.1, 如何在五个数中用最快的速度找到中位数.
在这个问题中, 我们先要定义什么是"快". 事实上, 计算机在"找第几大的数", "选择最大值/最小值", "排序"这几个操作中, 往往是不断地对数字进行两两比较, 而得出结果的. 在这个问题中, 我们且把速度定义为对数字的两两比较的次数.
Problem 1.1的分析
该问题等价于找到最小的比较次数k, 使得五个两两不同的数在不超过k次比较中可以找到中位数.
由于五个数的中位数要大于其中两个数而小于另外两个数. 所以这里出现了四个大小关系, 对应了我们至少要进行四次比较来得到中位数. 那么, 我们是否可以随机挑一个数x, 然后把x和其他四个数比较呢? 显然是不行的, 因为x如果不是中位数, 那么这个策略就失败了.
上面的分析给了我们两点基础结论. (1) k至少是4. (2) 如果只进行4次比较, 则不能在4次比较中都包含同一个元素. 事实上, (2)蕴含了一个结论, 最优解中必定存在四个不同元素, a和b. c和d比较过 (标记为结论*). 因为如果进行5次以上比较的话则显然; 如果进行4次, 而不能用(2)的比较方法的话, 这个结论也是成立的.
根据结论*, 我们假定对两个数做第一次比较, 把小的记做a, 大的记做b, 则有a<b. 再选取另外两个数用同样的方法记做c<d. 而并未比较的那个数记做e.
在这种情况下我们初步分析了如何进行比较的策略. 层层递推下去, 不难发现一个比较次数是6的解法. 我在这里做一个举例.
比较a和c, 由对称性得到 a<c. 这样我们有三个条件了, a<b, a<c<d. 那么对于5个数的所有排列(permutation)来讲, 也只有15个排列符合条件了.
在这个问题中, 我们先要定义什么是"快". 事实上, 计算机在"找第几大的数", "选择最大值/最小值", "排序"这几个操作中, 往往是不断地对数字进行两两比较, 而得出结果的. 在这个问题中, 我们且把速度定义为对数字的两两比较的次数.
Problem 1.1的分析
该问题等价于找到最小的比较次数k, 使得五个两两不同的数在不超过k次比较中可以找到中位数.
由于五个数的中位数要大于其中两个数而小于另外两个数. 所以这里出现了四个大小关系, 对应了我们至少要进行四次比较来得到中位数. 那么, 我们是否可以随机挑一个数x, 然后把x和其他四个数比较呢? 显然是不行的, 因为x如果不是中位数, 那么这个策略就失败了.
上面的分析给了我们两点基础结论. (1) k至少是4. (2) 如果只进行4次比较, 则不能在4次比较中都包含同一个元素. 事实上, (2)蕴含了一个结论, 最优解中必定存在四个不同元素, a和b. c和d比较过 (标记为结论*). 因为如果进行5次以上比较的话则显然; 如果进行4次, 而不能用(2)的比较方法的话, 这个结论也是成立的.
根据结论*, 我们假定对两个数做第一次比较, 把小的记做a, 大的记做b, 则有a<b. 再选取另外两个数用同样的方法记做c<d. 而并未比较的那个数记做e.
在这种情况下我们初步分析了如何进行比较的策略. 层层递推下去, 不难发现一个比较次数是6的解法. 我在这里做一个举例.
比较a和c, 由对称性得到 a<c. 这样我们有三个条件了, a<b, a<c<d. 那么对于5个数的所有排列(permutation)来讲, 也只有15个排列符合条件了.
\begin{array}{ccccc} eacbd (A)&aecbd (A)&acebd (B)&acbed (C)&acbde (C)\\ eabcd (D)&aebcd (D)&abecd (E)&abced (C)&abcde (C)\\ eabdc (D)&aebdc (D)&abedc (E)&abdec (F)&abdce (F)\\ \end{array}
我们把这个15个排列用ABCDEF做标注. 第四步的比较将在b和e中进行, 这样我们就把ABD和CEF分开了.
对于剩下的两步来说, 只剩下我们可以
比较b和c分开ABD;
比较c和e分开AB;
比较c和e分开C和EF;
比较d和e分开E和F.
而对于ABCDEF每一个集合, 它们的中位数都是一致的. 这样我们就巧妙地利用6次比较, 找到了5个数的中位数.
对于剩下的两步来说, 只剩下我们可以
比较b和c分开ABD;
比较c和e分开AB;
比较c和e分开C和EF;
比较d和e分开E和F.
而对于ABCDEF每一个集合, 它们的中位数都是一致的. 这样我们就巧妙地利用6次比较, 找到了5个数的中位数.
这个解法看似比较复杂, 而实际上从白纸开始也不难推导出来.
首先前两次比较是一个比较显然的结论;
其次, 在之后的每一次比较中都以拿到最大的信息为目标逐步递进, 这样基本上就在正确的方向上了.
注意, 在这个问题中, 我们其实是在对5个数的全排列的集合做分割, 直到剩下的每一个集合中都只有唯一的中位数.
排列的分割(division on Permutations)
拿到一种排列方法之后, 一个问题就自然而然地产生了. 这个方法是最优的么? 会不会存在一种方法, 使用更少的比较次数而找到确切的中位数呢?
为了探究我们的方法是不是最优的, 我们必须对这个问题采用严谨的分析. 事实上, 上述的结论*是可靠的. 我们从结论*出发, 来推一下剩下情况的可能性.
第三个比较, b和e的比较实际上是必要的. 因为无论如何, 必定存在一个比较, 并且e参与其中. 那么, e和a,b,c,d比较是具有对称性的 (小于和大于也是对称的).所以, b和e的比较是一个对称性压缩的结果. 而仔细观察上表中的三次比较之后所剩的15个排列. 这15个排列中有5个不同的中位数, (BE一个, ACDF各一个), 而每一次比较只能将排列的集合分成两类, 所以两次比较不可能将这15个排列分成5类.
这样我们就证明了, 我们上述的解法是最优的.
Problem1.1的解
最少的比较次数是6次.
先比较两对数, 并标记a<b, c<d;
再比较b和e. 如果b大, 则依次比较bc和ce;
如果e大, 则依次比较ce和de.
上述论述证明了不存在比6次比较更少的比较次数.
事实上, 我们可以把这个找中位数的问题看做是一个和比较排序(comparison sort)类似, 但是较为简单的问题. 这两个问题有一个共同点: 它们的本质都是在对序列的全排列进行分割, 并且每次比较只能将现有的每一个集合分割成不超过两个. 基于这一点, 我们可以推导出比较排序的时间复杂度的下界.
排序问题的起始则是一个全排列的集合, 这个集合的势是n!. 其目标是将这个集合最终分割成n!个单元集合, 每个集合恰好包含这个序列的一个排列.
Problem2.1的解
比较排序的本质是将n个数的全排列分割成若干个集合, 每个集合里只有唯一的排列. 由于n个数的全排列最多有n!种, 而每一次比较最多可以将现有的每一个集合分割成不超过两个. 所以比较排序的时间复杂度的下界为 O(log(n!)) = O(n log(n)).
归并排序是一个时间复杂度为O(n log(n))的比较排序, 所以上述下界即为下确界.
为了探究我们的方法是不是最优的, 我们必须对这个问题采用严谨的分析. 事实上, 上述的结论*是可靠的. 我们从结论*出发, 来推一下剩下情况的可能性.
第三个比较, b和e的比较实际上是必要的. 因为无论如何, 必定存在一个比较, 并且e参与其中. 那么, e和a,b,c,d比较是具有对称性的 (小于和大于也是对称的).所以, b和e的比较是一个对称性压缩的结果. 而仔细观察上表中的三次比较之后所剩的15个排列. 这15个排列中有5个不同的中位数, (BE一个, ACDF各一个), 而每一次比较只能将排列的集合分成两类, 所以两次比较不可能将这15个排列分成5类.
这样我们就证明了, 我们上述的解法是最优的.
Problem1.1的解
最少的比较次数是6次.
先比较两对数, 并标记a<b, c<d;
再比较b和e. 如果b大, 则依次比较bc和ce;
如果e大, 则依次比较ce和de.
上述论述证明了不存在比6次比较更少的比较次数.
事实上, 我们可以把这个找中位数的问题看做是一个和比较排序(comparison sort)类似, 但是较为简单的问题. 这两个问题有一个共同点: 它们的本质都是在对序列的全排列进行分割, 并且每次比较只能将现有的每一个集合分割成不超过两个. 基于这一点, 我们可以推导出比较排序的时间复杂度的下界.
排序问题的起始则是一个全排列的集合, 这个集合的势是n!. 其目标是将这个集合最终分割成n!个单元集合, 每个集合恰好包含这个序列的一个排列.
Problem2.1的解
比较排序的本质是将n个数的全排列分割成若干个集合, 每个集合里只有唯一的排列. 由于n个数的全排列最多有n!种, 而每一次比较最多可以将现有的每一个集合分割成不超过两个. 所以比较排序的时间复杂度的下界为 O(log(n!)) = O(n log(n)).
归并排序是一个时间复杂度为O(n log(n))的比较排序, 所以上述下界即为下确界.
对归并排序的时间复杂度分析见下文.
比较排序(Comparing Sort)
比较排序是一种排序方法的统称, 这些排序方法的共同特点是, 它们通过多次进行比较两个元素之间大小的方法来确定最终的序列. 我们在上文中得知, 比较排序所需的最少的比较次数是O(n log(n)), 那么, 一些典型的比较排序算法是怎么样实现排序的呢? 我们先讲几个简单的排序算法, 然后再结合分治法讲一些高效的排序算法.
我们知道, 在一个序列中找出其最小值/最大值, 是扫描一遍这个序列就可以得到的. 那么, 一个很自然的算法, 则是每次从序列中把最小值找出来, 然后将其删掉; 那么进行n次查找/删除操作之后得到的这个由找出来的元素构成的新的序列则是一个排好序的序列. 这种方法叫做选择排序(selection sort). 由于一次查找操作的时间复杂度是O(n), 所以选择排序的时间复杂度是O(n^2). (这里删除操作的时间复杂度被默认为O(1), 如果采用一般的随机存取线性数据结构来存储序列的话)
另一种办法则每次从序列中取一个元素出来, 然后将选出来的元素插入由已取出元素构成的排好序的序列, 直到所有的元素都被取出为止. 这种办法类似于玩扑克牌时的排序方法, 即每次抓一张牌, 然后把它插入已经抓好的, 排好序的牌中. 这里取元素操作占用O(1)的时间, 插入的时间则是O(n), 所以插入排序的时间复杂度是O(n^2). (仍然假定使用一般的随机存取线性数据结构)
还有一种排序方法叫做冒泡排序. 如果从左到右地对每两个相邻的元素进行比较, 并且把大的放在右边的话, 那么一轮则一定可以把最大的元素放在序列的最右端. 这个操作被称之为冒泡, 每次通过尝试交换来最终确定一个最大的元素(最小的亦可), 而被冒出来的这个最大的元素则属于已经排好的序列. 这样, 不断地对未排好的部分进行冒泡, 则我们可以使用n-1次冒泡来完成排序. 冒泡排序的一次冒泡时间是O(n), 共进行n次冒泡, 所以其时间复杂度是O(n^2).
我们知道, 在一个序列中找出其最小值/最大值, 是扫描一遍这个序列就可以得到的. 那么, 一个很自然的算法, 则是每次从序列中把最小值找出来, 然后将其删掉; 那么进行n次查找/删除操作之后得到的这个由找出来的元素构成的新的序列则是一个排好序的序列. 这种方法叫做选择排序(selection sort). 由于一次查找操作的时间复杂度是O(n), 所以选择排序的时间复杂度是O(n^2). (这里删除操作的时间复杂度被默认为O(1), 如果采用一般的随机存取线性数据结构来存储序列的话)
另一种办法则每次从序列中取一个元素出来, 然后将选出来的元素插入由已取出元素构成的排好序的序列, 直到所有的元素都被取出为止. 这种办法类似于玩扑克牌时的排序方法, 即每次抓一张牌, 然后把它插入已经抓好的, 排好序的牌中. 这里取元素操作占用O(1)的时间, 插入的时间则是O(n), 所以插入排序的时间复杂度是O(n^2). (仍然假定使用一般的随机存取线性数据结构)
还有一种排序方法叫做冒泡排序. 如果从左到右地对每两个相邻的元素进行比较, 并且把大的放在右边的话, 那么一轮则一定可以把最大的元素放在序列的最右端. 这个操作被称之为冒泡, 每次通过尝试交换来最终确定一个最大的元素(最小的亦可), 而被冒出来的这个最大的元素则属于已经排好的序列. 这样, 不断地对未排好的部分进行冒泡, 则我们可以使用n-1次冒泡来完成排序. 冒泡排序的一次冒泡时间是O(n), 共进行n次冒泡, 所以其时间复杂度是O(n^2).
三种基础排序算法中, 由于选择排序的时间消耗是和原序列存储方式相关的, 而插入排序的时间消耗是和新的"已取出的元素构成的排好序的序列"的存储方式相关. 所以两个排序方法的时间效率可以因这两个序列的存储方式而优化.
比如, 在选择排序中, 如果先把原序列存进一个最大堆/最小堆中, (插入时间O(log(n)), 选择最大/最小值时间O(1), 取出/删除时间O(log(n)), 再逐个将最大/最小值取出的话, 那么它的时间复杂度则被优化为O(n(log(n)). 这个方法又叫做堆排序.
再如, 如果在插入排序中使用二叉树来存储取出元素(平均插入时间O(log(n)), 最坏插入时间O(n), 二叉树打印序列时间O(n)), 并在最后将其序列打印出来的话, 那么得到了一个平均时间复杂度O(n log(n))而最坏时间复杂度O(n^2)的排序方法. 这个方法叫做二叉树排序.
上述的二叉树排序可以用更高级的, 具有平衡操作的平衡二叉树来代替, 这样的话最坏插入时间也缩减到了O(log(n)), 整个排序的时间复杂度变成了O(n log(n)). 即平衡二叉树排序.
前文中所提及的一系列排序算法, 其每轮操作都是挑选出一个元素. (冒泡排序本质是一轮选出一个最值) 那么, 有没有更好的策略来对这个序列进行排序呢?
快排与归并排序(Quick-sort & Merge-sort)
我们在算法漫谈的第二节, 矩阵方幂与矩阵乘法这一个部分里, 提到了分治法(Divide and Conquer)来将主问题划归成多个子问题的策略. 事实上, 这个策略同样可以广泛应用于排序方法里.
在我们拿到一个序列之后, 一个很自然的分治思想是, 可否把这个序列分成两份, 而分别处理呢? 基于这个分治思想, 我们可以联系到两种不同的排序思想.
第一, 我们挑出一个元素, 把比这个元素小的所有元素作为一个子序列进行递归, 排好之后放在它左边; 把其它比这个元素相等或者大的所有元素作为一个子序列进行递归排序, 排好放在它右边.
第二, 我们把这个序列左边的一般进行递归, 使得其左边一半已经排好; 右边一半也这样做; 然后我们把排好的两个子序列进行合并, 这样就可以排好整个序列.
第一种方法对应快速排序, 第二种方法对应归并排序. 以归并排序为例, 一次合并操作所需要的时间是O(n), 而假设归并排序的时间复杂度是T(n)的话, 则可以得到T(n) = 2T(n/2)+O(n). 这个递推公式对应T(n) = O(n log(n)), 换而言之, 归并排序由于其分割的均匀性, 递归的层数会被恰好限制在O(log(n))层.
事实上, 如果完美利用分而治之的思想, 则我们总可以通过O(log(n))层递归来解决这个排序问题. 然而快速排序的时间复杂度分析则比归并排序要复杂很多. 注意, 在快速排序中存在一定概率, 使得挑选的这个元素恰好是最大值, 或最小值. 这样会导致"分而治之"的这两个序列一个是空的, 而另一个具有n-1的长度. 那么最坏情况下我们需要递归n-1层, 即快速排序的最坏时间复杂度为O(n^2).
那么快速排序的平均时间复杂度是多少呢? 我们可以认为快速排序中, 挑选的元素会把序列分成两份, 长度分别为 q 和 n-1-q, q在0到n-1上面均匀分布. 即:
在我们拿到一个序列之后, 一个很自然的分治思想是, 可否把这个序列分成两份, 而分别处理呢? 基于这个分治思想, 我们可以联系到两种不同的排序思想.
第一, 我们挑出一个元素, 把比这个元素小的所有元素作为一个子序列进行递归, 排好之后放在它左边; 把其它比这个元素相等或者大的所有元素作为一个子序列进行递归排序, 排好放在它右边.
第二, 我们把这个序列左边的一般进行递归, 使得其左边一半已经排好; 右边一半也这样做; 然后我们把排好的两个子序列进行合并, 这样就可以排好整个序列.
第一种方法对应快速排序, 第二种方法对应归并排序. 以归并排序为例, 一次合并操作所需要的时间是O(n), 而假设归并排序的时间复杂度是T(n)的话, 则可以得到T(n) = 2T(n/2)+O(n). 这个递推公式对应T(n) = O(n log(n)), 换而言之, 归并排序由于其分割的均匀性, 递归的层数会被恰好限制在O(log(n))层.
事实上, 如果完美利用分而治之的思想, 则我们总可以通过O(log(n))层递归来解决这个排序问题. 然而快速排序的时间复杂度分析则比归并排序要复杂很多. 注意, 在快速排序中存在一定概率, 使得挑选的这个元素恰好是最大值, 或最小值. 这样会导致"分而治之"的这两个序列一个是空的, 而另一个具有n-1的长度. 那么最坏情况下我们需要递归n-1层, 即快速排序的最坏时间复杂度为O(n^2).
那么快速排序的平均时间复杂度是多少呢? 我们可以认为快速排序中, 挑选的元素会把序列分成两份, 长度分别为 q 和 n-1-q, q在0到n-1上面均匀分布. 即:
$$ T(n) = O(n)+\Sigma_{q=0}^{n-1} (T(q) + T(n-1-q)) $$
经过一系列复杂的运算, 我们可以得到T(n) = O(n log(n)). 即, 快速排序的平均时间复杂度是O(n log(n))的.
这个快排平均时间复杂度的式子解起来不是很容易, 其大致思想是用两个O(n log(n))的函数来上下逼近T(n), 从而得到T(n) = O(n log(n))的结论.
有兴趣的读者可以参照算法导论的相关章节.
我们可以看到, 分治思想在排序算法中可以很大地提高排序的效率. 在不借助高级数据结构的情况下, 使用分治法进行快速排序/归并排序, 可以将其平均的递归层数限制到O(log(n))的级别上, 从而得到平均时间复杂度是O(n log(n))的排序策略.
两个性质(Two Properties)
我们再讨论一下比较排序算法的两个性质.
就地排序(inplace sorting)是指在只允许额外使用常数空间的情况下完成排序. 这种情况下不能额外建立一个新的序列, 或是一个高级数据结构. 冒泡排序是一种典型的就地排序; 朴素的, 不使用高级数据结构的选择排序和插入排序都可以实现成就地的排序; 快速排序可以通过大量的交换操作实现成就地排序.
我们的题目 Problem 3.1 就有就地排序的要求. 在后文中, 我们将采用一系列交换操作的策略, 来用就地排序的方式实现对这个问题的解答.
稳定排序(stable sorting)是指如果一个序列中有若干个大小相同的元素, 则他们在排序算法中相对位置不发生改变. 在算法的运行过程中, 对未排好序的序列进行远距离元素交换, 是导致排序算法不稳定的重要原因.
冒泡排序如果大小相同的相邻元素不交换, 则为稳定排序; 选择排序和插入排序则可以实现成稳定排序; 归并排序可以实现成稳定排序; 朴素的, 就地的快速排序是不稳定排序, 但快速排序有实现成稳定排序的空间.
就地排序(inplace sorting)是指在只允许额外使用常数空间的情况下完成排序. 这种情况下不能额外建立一个新的序列, 或是一个高级数据结构. 冒泡排序是一种典型的就地排序; 朴素的, 不使用高级数据结构的选择排序和插入排序都可以实现成就地的排序; 快速排序可以通过大量的交换操作实现成就地排序.
我们的题目 Problem 3.1 就有就地排序的要求. 在后文中, 我们将采用一系列交换操作的策略, 来用就地排序的方式实现对这个问题的解答.
稳定排序(stable sorting)是指如果一个序列中有若干个大小相同的元素, 则他们在排序算法中相对位置不发生改变. 在算法的运行过程中, 对未排好序的序列进行远距离元素交换, 是导致排序算法不稳定的重要原因.
冒泡排序如果大小相同的相邻元素不交换, 则为稳定排序; 选择排序和插入排序则可以实现成稳定排序; 归并排序可以实现成稳定排序; 朴素的, 就地的快速排序是不稳定排序, 但快速排序有实现成稳定排序的空间.
Problem 3.1的解(Solution to Problem 3.1)
显然, 使用一种时间复杂度为O(n log(n))的就地排序即可将Problem 3.1解决. 但是这个算法不一定满足最快的条件. 因为Problem 3.1中的序列只有0, 1, 2三种元素, 相比于一般的序列排序, 其全排列的个数只有3^n. 对这个全排列取对数, 即最小分割次数的话, 我们得到O(n log3) = O(n). 也就是说, Problem 3.1中的序列的排序时间复杂度下界是O(n), 我们有了充分的理由去探索线性的排序方法.
我们先考虑一个更简单的情况. 假如在Problem 3.1中, 只有0, 1两种元素的话, 我们可以如何排序.
答案比较简单, 一个不难想到的线性的排序方法即可实现. 假定我们采用一个指针a. 在任意时刻, 如果a对应的元素是0, 则让a一直右移. 我们清晰地看到, a左边的序列部分, 一定全部都是元素0.
那么, 如果a遇到1之后应该如何操作呢? 事实上, 我们需要找到一个右边的某个0与其交换(这里可以假设为是右边离a最近的0), 并且将a右移一格. 这样, 我们只要再使用一个指针a'就可以了.
一般地, a'是独立于a的另一个指针. 也是从左开始. 如果a向右移动超过了a', 则a'跟着向右移动, 保证其在a右面. 每当a遇到一个1时, a'不断向右移动, 直到找到第一个0, 那么这个0就是右边离a最近的0. 把这个0与a上的1交换, 并且将a右移一格.
这样我们保证了两个性质. 一个是前面提过的, a左边通通为0; 另一个则由于a'在寻找右边离a最近的0, 所以a和a'之间一定都是1. 这样的话, 当a'扫描完整个数组时, 则排序就完成了. 这个算法对序列从左到右只扫描了两次, 所以其复杂度为O(n).
现在我们解决了一个Problem 3.1的问题的简单版. 那么, 在有三个元素而不是两个的时候, 我们能否用类似的方法解决呢?
答案是肯定的, 我们只需要同样地使用两个指针b和b', 从序列的右端开始就可以了.
Solution 3.1
当n充分大时, 序列的全排列有3^n个, 所以其比较排序的时间复杂度下界是O(log(3^n)) = O(n). 我们下面提出一种O(n)的算法.
初始化4个指针, a, a', b, b'. 一开始a,a'都在序列的最左端, b,b'都在序列的最右端.
1) a遇0则向右移动; 如果a'在a左边或重合, 则a'也向右移动, 保证在a的右边;
2) b遇2则向左移动; 如果b'在b右边或重合, 则b'也向左移动, 保证在b的左边;
3) 当a遇到了非0, 且b遇到了非2时, 则a'和b'向中心移动: a'和b'跳过所有的1, 并在0或2的地方停下来. 如果a'和b'直到相遇都没有遇到0或者2, 则排序完成, 算法结束;
4) 如果a'和b'停了下来, 那么a'和b'指向的元素中, 必有0或者必有2; 如果有0, 则用0和a指向的元素交换. a继续右移; 如果有2, 则用2和b指向的元素交换, b继续左移.
5) 反复进行上述四个步骤, 直到a'和b'相遇, 则算法结束, 排序完毕.
我们先考虑一个更简单的情况. 假如在Problem 3.1中, 只有0, 1两种元素的话, 我们可以如何排序.
答案比较简单, 一个不难想到的线性的排序方法即可实现. 假定我们采用一个指针a. 在任意时刻, 如果a对应的元素是0, 则让a一直右移. 我们清晰地看到, a左边的序列部分, 一定全部都是元素0.
那么, 如果a遇到1之后应该如何操作呢? 事实上, 我们需要找到一个右边的某个0与其交换(这里可以假设为是右边离a最近的0), 并且将a右移一格. 这样, 我们只要再使用一个指针a'就可以了.
一般地, a'是独立于a的另一个指针. 也是从左开始. 如果a向右移动超过了a', 则a'跟着向右移动, 保证其在a右面. 每当a遇到一个1时, a'不断向右移动, 直到找到第一个0, 那么这个0就是右边离a最近的0. 把这个0与a上的1交换, 并且将a右移一格.
这样我们保证了两个性质. 一个是前面提过的, a左边通通为0; 另一个则由于a'在寻找右边离a最近的0, 所以a和a'之间一定都是1. 这样的话, 当a'扫描完整个数组时, 则排序就完成了. 这个算法对序列从左到右只扫描了两次, 所以其复杂度为O(n).
现在我们解决了一个Problem 3.1的问题的简单版. 那么, 在有三个元素而不是两个的时候, 我们能否用类似的方法解决呢?
答案是肯定的, 我们只需要同样地使用两个指针b和b', 从序列的右端开始就可以了.
Solution 3.1
当n充分大时, 序列的全排列有3^n个, 所以其比较排序的时间复杂度下界是O(log(3^n)) = O(n). 我们下面提出一种O(n)的算法.
初始化4个指针, a, a', b, b'. 一开始a,a'都在序列的最左端, b,b'都在序列的最右端.
1) a遇0则向右移动; 如果a'在a左边或重合, 则a'也向右移动, 保证在a的右边;
2) b遇2则向左移动; 如果b'在b右边或重合, 则b'也向左移动, 保证在b的左边;
3) 当a遇到了非0, 且b遇到了非2时, 则a'和b'向中心移动: a'和b'跳过所有的1, 并在0或2的地方停下来. 如果a'和b'直到相遇都没有遇到0或者2, 则排序完成, 算法结束;
4) 如果a'和b'停了下来, 那么a'和b'指向的元素中, 必有0或者必有2; 如果有0, 则用0和a指向的元素交换. a继续右移; 如果有2, 则用2和b指向的元素交换, b继续左移.
5) 反复进行上述四个步骤, 直到a'和b'相遇, 则算法结束, 排序完毕.
桶和基数排序(Bucket-sort & Radix-sort)
我们观察到, 当数域缩小到一定范围时, 例如Problem 3.1, 我们的排序速度可以加快. 一般地, 对于一个数域范围为m的长度为n的序列, 当n充分大时, 其全排列的个数是m^n. 那么, 我们可以得知其排序时间复杂度的下界是O(log(m^n)) = O(n log(m)).
注意一点区别. 在对Problem 3.1解答时, 我们虽然使用了排序, 但是并没有任何比较操作. 我们进行的其实是一种比"比较"更简单的操作, 即看一个元素是不是0, 是不是1, 或是不是2.
这样的排序不属于比较排序的范畴. 同理, 我们现在所谈及的基数排序也不是比较排序的范畴.
根据如上分析, 我们得到一种新的, 不基于比较的排序策略. 我们将数域m映射到log(m)个维度上, 则每一个维度的数域都是常数. 扫描整个序列 log(m) 次, 得到每个元素在每一个维度上的值. 上述过程即完成了对这个序列的排序.
为了弄清楚这个排序的过程, 我们举一个具体的例子. 假如我们有0到9的一堆数, 那么我们可以准备十个桶. 对于每一个数, 把它按照数值装进对应的桶内(插入时间O(1)), 之后我们按照桶0到桶9的办法把所有的数值收集下来(打印时间O(n)). 那么, 这个排序就完成了, 其时间复杂度为O(n). 这个排序叫做桶排序(bucket sort).
通常来讲, 桶排序的时间复杂度是O(nm), 就像上述例子一样, 不对数域m进行映射. 不过这个时间可以优化到O(n log(m)), 即基数排序(radix sort), 或者多维的桶排序. 这log(m)维的空间的每一维对应基数排序概念中的基数.
比如我们现在有一些自然数, 在0 ~ 9,999,999之间. 那么现在这个自然数数域有7位, 我们就打算对它们递归地排7轮. 第一轮观察它们的最高位, 即百万位, 准备10个桶, 分桶装好后得到10组数, 这10组数的组组之间已经排序完毕.
之后我们递归地对十万位进行桶排序, 排好后继续递归, 直到每一位都排序完毕. 之后用O(n)的时间打印出来. 这个对不超过7位的自然数的, 时间复杂度为O(n log(m))的排序, 就是一个典型的基数排序.
当然了, 基数排序对属于要求比较苛刻, 更不能用于一些无限数域的元素之间的排序. 往往只有在数域范围远远小于序列的长度时, 才使用这个方法, 否则得不偿失.
为了弄清楚这个排序的过程, 我们举一个具体的例子. 假如我们有0到9的一堆数, 那么我们可以准备十个桶. 对于每一个数, 把它按照数值装进对应的桶内(插入时间O(1)), 之后我们按照桶0到桶9的办法把所有的数值收集下来(打印时间O(n)). 那么, 这个排序就完成了, 其时间复杂度为O(n). 这个排序叫做桶排序(bucket sort).
通常来讲, 桶排序的时间复杂度是O(nm), 就像上述例子一样, 不对数域m进行映射. 不过这个时间可以优化到O(n log(m)), 即基数排序(radix sort), 或者多维的桶排序. 这log(m)维的空间的每一维对应基数排序概念中的基数.
比如我们现在有一些自然数, 在0 ~ 9,999,999之间. 那么现在这个自然数数域有7位, 我们就打算对它们递归地排7轮. 第一轮观察它们的最高位, 即百万位, 准备10个桶, 分桶装好后得到10组数, 这10组数的组组之间已经排序完毕.
之后我们递归地对十万位进行桶排序, 排好后继续递归, 直到每一位都排序完毕. 之后用O(n)的时间打印出来. 这个对不超过7位的自然数的, 时间复杂度为O(n log(m))的排序, 就是一个典型的基数排序.
当然了, 基数排序对属于要求比较苛刻, 更不能用于一些无限数域的元素之间的排序. 往往只有在数域范围远远小于序列的长度时, 才使用这个方法, 否则得不偿失.