1. 比较排序算法的下界
比较排序
到目前为止，已经介绍了几种能在O(nlgn)时间内排序n个数的算法：归并排序 和 堆排序 达到了最坏情况下的上界；快速排序 在平均情况下达到该上界。
如果仔细观察会发现：在排序的最终结果中，各元素之间的次序依赖于它们之间的比较。我们把这类排序算法统称为 **比较排序(counting-sort)**。到目前为止介绍的排序算法都是 比较排序。下面会论证一个事实：任何 比较排序 算法在最坏情况下都要经过Ω(n lgn)次比较。
决策树模型
在证明之前，先介绍一种由 比较排序 抽象而来的 决策树模型。决策树 是一棵完全二叉树，它可以表示在给定输入规模情况下，某一特定 排序算法 对所有元素的比较操作，而控制，数据移动等操作都被忽略了。如下图，它显示的是插入排序算法作用于包含三个元素的输入序列的决策树情况。
最坏情况下的下界
从 决策树 中我们可以看出：从根结点到任意一个可到达叶结点之间的最长简单路径的长度，表示的就是对应排序算法中最坏情况下的比较次数。因此，一个 比较排序 算法中的最坏情况的排序次数就等于 决策树 的高度。并且，当 决策树 中所有排列都是以可到达的叶结点的形式出现时，该 决策树 高度的下界也就是 比较排序 算法运行时间的下界。下面正式给出证明。
考虑一棵高度为h，具有l个可到达叶结点的决策树。它对应一个对n个元素进行的比较排序。因为输入数据有n！种可能的排列都是叶结点，所以 。由于在一棵高度为h的二叉树中，叶结点的数目不多于 ，我们得到：
两边取对数得：
2. 计数排序
先假设待排序序列各元素均在区间 [0, k] 上。
计数排序的思想是：在待排序序列中，如果能统计出有多少元素小于或等于某一个元素，也就知道了该元素的正确位置。例如，对于待排序序列{2,5,3,0,2,3,0,3}，统计出有8个元素小于等于5（包括5自己），那么5这个元素就应该被排序到第8位。
下面给出算法的伪代码描述：
其中数组A[1 ~ n]是待排序数组；数组B[1 ~ n]用来存放已排好序的元素。C[0 ~ k]用来存放上面所说的统计数（具体的说C[i]就表示在数组A中，小于或等于i的元素的总个数）。
下面这幅图描述的是对序列{2,5,3,0,2,3,0,3}排序的过程：
下面给出算法的 Java 实现代码：
public static void main(String[] args) {
int[] array = { 2, 5, 3, 0, 2, 3, 0, 3 };
printArray(countingSort(array, 5));
}
/**
* 计数排序
*
* @param array
* 待排序数组(假定各元素的范围是0~max，包括0和max)
* @param max
* 待排序数组中的最大值
*/
public static int[] countingSort(int[] array, int max) {
int[] result = new int[array.length];
int[] temp = new int[max + 1];
// 以下循环操作完成后，temp的第i个位置保存着array中，值为i的元素的总个数
for (int i : array) {
temp[i]++;
}
// 以下循环操作完成后，temp的第i个位置保存着array中，值小于或等于i的元素的总个数
for (int i = 1; i < temp.length; i++) {
temp[i] += temp[i - 1];
}
for (int i = array.length - 1; i > -1; i--) {
result[temp[array[i]] - 1] = array[i];
temp[array[i]]--;
}
return result;
}
/**
* 打印数组
*/
public static void printArray(int[] array) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
}
3. 算法分析
现在来分析 计数排序 的时间代价。
在伪代码中，第2~3行时间代价Θ(k)；第4到5行时间为Θ(n)；第7到8行时间为Θ(k)，第10到12行时间为Θ(n)。因此，总的运行时间是Θ(k+n)。当k= O(n)时，运行时间为Θ(n)。
可以看出，计数排序的下界优于我们上面论证的比较排序算法的下界时间Ω(nlgn)。这是因为计数排序并不是比较排序算法。事实上，在代码中从未出现比较某两个元素大小的代码。相反，计数排序是使用输入元素的实际值来确定其在数组中的位置。此时，比较排序算法的模型对计数排序不再适用。