1. 非比较排序插入排序、归并排序、堆排序、快速排序这四种排序算法，他们的运行时间上界不会超过O(nlgn)。这些算法都有一个有趣的性质：在排序的最终结果中，各元素的次序依赖于它们之间的比较。我们把这类排序算法称为比较排序。 可以证明，基于比较的排序算法在最坏情况下的时间下界是Ω(nlgn)。堆排序和归并排序的运行时间上界为O(nlgn)，因此这两种排序算法都是渐进最优的比较排序算法。 而非基于比较的排序，如计数排序，桶排序，和在此基础上的基数排序，则可以突破O(NlogN)时间下限，达到线性时间复杂度$$O(n)$$。但要注意的是，非基于比较的排序算法的使用都是有条件限制的，例如元素的大小限制，相反，基于比较的排序则没有这种限制(在一定范围内)。但并非因为有条件限制就会使非基于比较的排序算法变得无用，对于特定场合有着特殊的性质数据，非基于比较的排序算法则能够非常巧妙地解决。 基数排序：O(dn) (d次调用桶排序)，空间复杂度 O(k) 桶排序：O(n)时间复杂度，O(n)空间复杂度 计数排序：O(n)时间复杂度，O(k)空间复杂度，每一个元素都是整数，并且位于0到k - 1之间 2. 计数排序计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。当k=O(n)时，排序的运行时间为Θ(n)。 计数排序的思想是，对每一个输入元素，计算小于它的元素个数，如果有10个元素小于它，那么它就应该放在11的位置上，如果有17个元素小于它，它就应该放在18的位置上。当有几个元素相同时，这一方案要略做修改，因为不能把它们放在同一个输出位置上。下图展示了实际的运行过程。 计数排序 构造辅助数组C，C的长度为k。第一次遍历A后，得到[0,k)区间上每个数出现的次数，将这些次数写入C，得到图(a)的结果。然后把C中每个元素变成前面所有元素的累加和，得到图(b)的结果。接下来，再次从后向前遍历数组A，根据取出的元素查找C中对应下标的值，再把这个值作为下标找到B中的位置，即是该元素排序后的位置。例如，图中A的最后一个元素是3，找到C[3]是7，再令B[7]=3即可，然后顺便把C[3]减一，这是防止相同的数被放到同一个位置。 计数排序的时间代价可以这样计算，第一次遍历A并计算C所花时间是Θ(n)，C累加所花时间是Θ(k)，再次遍历A并给B赋值所花时间是Θ(n)，因此，总时间为Θ(k + n)。在实际中，当k=O(n)时，我们一般会采用计数排序，这时的运行时间为Θ(n)。 3. 基数排序对于一组数据，我们可以按照每一位对它们进行排序。比如，考虑下面一组十进制数 先按最后一位从小到大排序，得到 再按中间一位从小到大排序，得到 最后按第一位从小到大排序，得到 其中，对任何一位的排序算法必须是稳定的，即相同数字不能改变它们的前后顺序。 基数排序算法的运行时间很容易计算，对于n个k进制d位数，假如每一位的排序使用计数排序算法，则该位排序用时为Θ(n + k)，总共d位数，总排序用时就是Θ(d(n + k))。当d为常数且k=O(n)时，总排序时间为Θ(n)。 4. 桶排序桶排序假设输入是由一个随机过程产生，该过程将元素均匀、独立地分布在[0,1)区间上。 我们将[0,1)区间划分为n个相同大小的子区间，称为桶。然后将输入数据分别放到各个桶中。如果数据分布得很均匀，每个桶中的数据就不会太多，都会维持在常数量级。我们先对每个桶中的元素排序，然后把所有桶中的元素顺序列出来即可。下图为n=10的一个案例。 桶排序.png 创建一个长度也为10的数组，将A中的元素按照大小找到B中合适的位置，插入链表。之后，分别对B中每个链表中的元素执行插入排序。最后将B中的所有元素依次取出即可。 现在分析桶排序的时间代价。将A中元素放入B用时Θ(n)，B中每个链表执行插入排序的用时，可以证明是O(2 - 1/n)，于是总用时就是Θ(n) + n * O(2 - 1/n) = Θ(n)。具体证明过程比较难理解，这里我想给出一个容易理解的解释，虽然不一定对，但还是可以帮助理解为什么总用时是Θ(n)。n个数放入n个桶，平均下来每个桶只有一个数，在实际中，可能有的多有的少，但都不会差得太离谱。因此我们可以认为每个桶中只有常数个数，那么对常数个数执行插入排序所用的时间当然也就是O(1)了。于是n个桶总用时就是O(n)，加上前面的Θ(n)，桶排序总用时就是Θ(n)了。 |
|
|
