整型序列排序到底有多快?
稍微对算法研究的人应该知道,在通用算法中,随机快速排序有着最好的时间效率,为O(nlgn)。但是如果对问题做一个限制,假设输入的序列长值为32位的无符号型整数,那么对这样的序列进行排序,时间复杂度是多少了?
为了处理这个问题,我们首先要介绍两种不是太常用的排序:计数排序以及稳定排序。
一、计数排序
计数排序是一种典型的空间换时间的排序方案。假设排序序列为:
A {x1, x2, x3, …, xn}
并且对A中任意元素xi;满足xi<k;
解决方案:
count = int[k] for v <-- xi count[v] ++ icount = k; for i in [n, ..., 1] while(k) if count[k] > 0 B[i] = k count[k]-- break else k--
计数排序的时间复杂度为O(n)实际上需要考虑xi<k这一个强限制条件,其时间效率为T(n)=k+n
对于32位整型,k达到4亿大小,导致这个排序在时间以及空间复杂度上是不可行的。
但是,如果是8位整型,k=256,那么这个算法将有着极高的效率。
那么我们可以将一个32整型分解为4个8位整型,如果有一种算法能够对4个一组的数据进行快速排序,那么这个问题就迎刃而解了。
幸运的是,我们能够找到这样的一个算法,这要感谢IBM的创始人。
稳定排序
稳定排序就是这样一种算法。稳定排序又叫尾排序,即排序时先排列最低位。
对于一个整型,需要使用4次稳定排序才能将数据进行重排。
综合两种算法,对整型的最快排序为时间为:
1024+4n
这是一个T(n)=O(n)的算法。