【算法导论】排序 （四）：决策树、线性时间排序(计数、基数、桶排序)

到目前为止，一共整理总结了五大排序算法：

1、插入排序

2、冒泡排序、选择排序、交换排序（把这三种方法归为一种，因为他们的思想本质上都是一样的）

3、归并排序

4、堆排序

5、快速排序

以上五种排序都可以称为“比较排序”，顾名思义，因为他们都是基于比较元素来决定其相对位置的。

其中前两种的时间为O（n^2），归并排序和堆排序最坏O( n lg n )，快排平均O( n lg n )

定理：任意一种比较排序算法最坏情况下，都需要做 Ω( n lg n )次的比较。

我们通过决策树来证明：

●决策树（decision tree）

比较排序可以被抽象的视为决策树。撒一颗决策树是一颗满二叉树，表示某排序算法作用于给定输入元素所作的所有比较，而其它因素忽略。

假设有一组三个元素的序列,我们用1，2，3来分别表示这三个元素，我们基于比较来对它排序，可以有下列决策树：

不难发现，判定树的叶子表示了三个元素的所有可能排列。
另外，用比较排序对这三个元素进行排序的话，你总可以找到一条路径来表示它的整个比较过程。（需要注意的是，1并不表示它代表第一个元素，它可以代表三个元素中任意一个。2，3也相同。但是1，2，3不指向相同元素）。显然最坏情况下的复杂度即是判定树的高。

对于一颗高度为H的、具有L个可达叶节点的决策树，它对应于对N个元素所作的比较排序。因为N个元素有N！种排列（排列组合知识）， 每一种都作为一个叶子出现在书中，故有N!<=L(重要,注：)有又由于在一颗高为H的二叉树中，叶子的数目不多于2^H,则有 N! <= L <= 2^H

对该式子取对数,得到：

H>=lg(N！) (因为lg函数时单调递增的)
=Ω(N lg N)

注： 一开始我以为应该是等于的关系，后来百度了一下，原文有这一句：Because each of the N! permutation appears as areachable leaf. 作者的意思着重于用N！来表示N个元素的所有可能排列，但是N个元素的所有可能排列实际上是小于等于N！的，因为在N个元素中有可能有相等的元素。

六、计数排序

基本思想：对每一个输入元素x，确定出小于x的元素个数。有了这一信息，就可以把x直接放到它在最终输出数组的位置。

稳定性：稳定的。

使用：计数排序假设n个输入元素中的每一个都是介于0到k之间的整数

时间：当k=n时(k是所有元素中最大的一个)，计数排序变得运行时间为O（n）.

在代码中，假定输入是个数组A【1...n】, length【A】=n. 另外还需要一个存放排序结果的数组B【1...n】,以及提供临时存储区的C【0...k】。

C++实现：

// 计数排序
#include<cstdio>
#include<algorithm>
using namespace std;
   
// n为数组元素个数，k是最大的那个元素
void CountingSort(int *input, int size, int k){
     
    int i;
    int *result = new int[size];  // 开辟一个保存结果的临时数组
    int *count = new int[k+1];  // 开辟一个临时数组
    for(i=0; i<=k; ++i)
        count[i]=0;
 
    // 使count[i]等于等于i的元素的个数
    for(i=0; i<size; ++i)
        ++count[input[i]];        // count数组中坐标为元素input[i]的增加1，即该元素出现的次数加1
     
    for(i=1; i<=k; ++i)
        count[i] += count[i-1];
 
    for(i=size-1; i>=0; --i){        // 正序来也行，但是到这来可以使排序是稳定的
		--count[input[i]];        // 因为数组下标从0开始，所以这个放在前面
        result[count[input[i]]] = input[i];   // 这个比较绕， count[input[i]-1] 就代表小于等于元素input[i]的元素个数，就是input[i]在result的位置   
    }
    copy(result,result+size,input);  // 调用copy函数把结果存回原数组
 
    delete [] result;  // 记得释放空间
    delete [] count;  
}
  
int main()
{
    int input[11]={2,7,4,9,8,5,7,8,2,0,7};  
    CountingSort(input,11,9);
    for(int i=0; i<11; ++i)
        printf("%d ",input[i]);
    putchar('\n');
    return 0;
}

这个实现对书上给的伪代码稍微改了一点， 如果计数排序如果每次要自己另外开一个数组保存结果才能用，感觉肯定很不爽。 所以在计数排序里面，把结果在拷贝到原来的数组。这样用的时候不用自己开数组，方便多了

我这里有一个更简单的" 计数排序 "，也可以实现排序。但是这个却又不太像计数排序。到底这个算不算是计数排序呢？ 这个问题也困扰了我很长时间，终于在某一天让我给发现了。 这个再后面再讲。 先把这个取名为“计数排序特殊版”

// n为数组元素个数，k是最大的那个元素
void CountingSort(int *input, int size, int k){
	
	int i;
	int *count = new int[k+1];
	for(i=0; i<=k; ++i)
		count[i]=0;
	
	for(i=0; i<size; ++i)
		++count[input[i]];
	
	int index=0;
	for(i=0; i<=k; ++i){  // 这个和上面的区别
		while(count[i]--){
			input[index++] = i;
		}
	}
	delete[] count;
}

七、基数排序

原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。

算法复杂度：对于n个d位数而言,如果基数排序的Stable Sort的算法复杂度为θ(n+k)，那么其本身的算法复杂度为θ(dn+kd)。这个就不用证明了。

实现方式：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

基数排序是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化"以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。

在之前两种比较排序——合并排序与快速排序中我们使用一种“分而治之”的策略，基数排序则使用另一种与之有有异曲同工之妙的策略。无论是合并排序还是快速排序，我们讲究的是在数组级别的“分而治之”；而基数排序我们讲究的是在元素级别的“分而治之”，例如我们将一个三位数分成，个位，十位，百位三部分。
我们先来看一个实例，假如，我们要对七个三位数来进行排序，依次对其个位，十位，百位进行排序，如下图：

很显然，每一位的数的大小都在[0，9]中，对于每一位的排序用计数排序再适合不过。

这里有一个基数排序的动画演示，挺不错的：http://www.jcc.jx.cn/xinwen3/news/kj/flash/2008/1126/1307.htm

《算法导论》上说，基数排序的代码是很简单的,给出的代码也很简单：

以下是用C++实现的基数排序代码：

#include <cstdio>
#include <cstdlib>
 
 
// 这个是基数排序用到的计数排序，是稳定的。
// pDigit是基数数组,nMax是基数的上限，pData是待排序的数组， nLen是待排序数组的元素个数
// 必须pDigit和pData的下标相对应的，即pDigit[1]对应pData[1]
int RadixCountingSort(int *pDigit, int nMax,int *pData,int nLen){
 
    // 以下是计数排序
    int *pCount = new int[nMax];
    int *pSorted = new int[nLen];
 
    int i,j;
    for(i=0; i<nMax; ++i)
        pCount[i] = 0;
 
    for(i=0; i<nLen; ++i)
        ++pCount[pDigit[i]];
 
    for(i=1; i<nMax; ++i)
        pCount[i] += pCount[i-1];
 
    for(i=nLen-1; i>=0; --i){
        --pCount[pDigit[i]];
        pSorted[pCount[pDigit[i]]] = pData[i];  // z这里注意，是把待排序的数组赋值
    }
 
    for(i=0; i<nLen; ++i)
        pData[i] = pSorted[i]; 
 
    delete [] pCount;
    delete [] pSorted;
    return 1;
}
 
int RadixSort(int *pData, int nLen){
 
    int *pDigit = new int[nLen]; // 申请存放基数(某个位数)的空间
 
    int nRadixBase = 1;  
    bool flag = false;
 
    while(!flag){
        flag = true;
        nRadixBase *= 10;
         
        for(int i=0; i<nLen; ++i){
            pDigit[i] = pData[i]%nRadixBase; // 求出某位上的数当做基数
            pDigit[i] /= nRadixBase/10;
            if(pDigit[i] > 0)
                flag = false;
        }
        if(flag)
            break;
        RadixCountingSort(pDigit,10,pData,nLen);
    }
 
    delete[] pDigit;
    return 1;
}
 
 
main()
{  
    int nData[10]={43,65,34,5,8,34,23,0,45,34};;
 
    RadixSort(nData, 10);
    printf("经排序后的数列是：\n");
    for (int  i = 0; i < 10; ++i)
        printf("%d ", nData[i]);
    printf("\n");
    return 0;
}

八、桶排序(箱排序)

思想: 把区间[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0，1)上，所以一般不会有很多数落在 一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列 出来即可。

复杂度：平均情况下桶排序以线性时间运行。像计数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分部分的时间复杂度都为O(n);很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

可以证明，即使选用插入排序作为桶内排序的方法，桶排序的平均时间复杂度为线性。具体证明，请参考算法导论。其空间复杂度也为线性。

假设有一组长度为N的待排关键字序列K[1....n]，首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i)，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。

比如考试分数通常为0-100分，我们可以建立11个桶，然后确定映射函数f(k)=k/10。则分数49将定位到第4个桶中(49/10=4)。

桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。应该尽量做到以下两点:
(1) 映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。
(2) 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

伪代码：

桶排序的动画演示：http://www.jcc.jx.cn/xinwen3/news/kj/flash/2008/1206/1309.htm

利用C++ STL的vector容器，我们就可以很容易地实现桶排序。

// 桶排序
#include<iostream>
#include<vector>
#include<iterator>
using namespace std;

void BucketSort(int *pData, int size){
	vector<int>Bucket[11];
	memset(Bucket,0,sizeof(0));
	int i,j,k,pos,key;
	for(i=0; i<size; ++i){ // 将每个元素插入到相应的桶中
		key=pData[i];
		pos = key/10;  // 求出该元素在哪个桶
		j=Bucket[pos].size()-1;
		Bucket[pos].push_back(key);  // 把该元素放入某个桶中
		while(j>=0 && Bucket[pos][j]>key){ // 用插入排序在某个桶里排序
			swap(Bucket[pos][j],Bucket[pos][j+1]);
			--j;
		}
	}
	k=0;
	for(i=0; i<11; ++i){
		for(j=0; j<Bucket[i].size(); ++j)
			pData[k++] = Bucket[i][j];
	}
}

int main()
{
	int arr[]={3,5,45,34,2,78,67,34,56,98};
	BucketSort(arr,10);
	for(int i=0; i<10; ++i)
		printf("%d ",arr[i]);
	printf("\n");
	return 0;
}

最后，现在再回顾一下我的那个“计数排序特殊版”：其实那是一个“特殊的桶排序”，一共有k个桶，然后把每个元素都放到对应的那个桶中。和一般的桶排序不同，这里每个桶放的都是相同的元素，所以最后不需要再用另外一个排序算法给每个桶再排序，直接把所有的桶合并在一起就是最终的排序了!

三种线性排序的比较：

从整体上来说，计数排序，桶排序都是非基于比较的排序算法，而其时间复杂度依赖于数据的范围，桶排序还依赖于空间的开销和数据的分布。而基数排序是一种对多元组排序的有效方法，具体实现要用到计数排序或桶排序。

相对于快速排序、堆排序等基于比较的排序算法，计数排序、桶排序和基数排序限制较多，不如快速排序、堆排序等算法灵活性好。但反过来讲，这三种线性排序算法之所以能够达到线性时间，是因为充分利用了待排序数据的特性，如果生硬得使用快速排序、堆排序等算法，就相当于浪费了这些特性，因而达不到更高的效率。

在实际应用中，基数排序可以用于后缀数组的倍增算法，使时间复杂度从O(N*logN*logN)降到O(N*logN)。线性排序算法使用最重要的是，充分利用数据特殊的性质，以达到最佳效果

终于把算法导论的八大排序总结完了。一共四篇，共四天时间。最后这一篇花的时间是最久的，其次是上一篇快速排序。总结学过的知识，是一件很有趣的过程，并且经过总结，才发现了自己还有很多地方不懂，。

马上就期末各种考试 + 英语四级了， 算法的学习将会暂停一段时间。如果在期末考试之前还能抽出时间， 把《算法导论》前两部分的最后一章“中位数和顺序统计学”再整理总结出来，这一章也和排序有很大的关系，并且也很有意思。

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double