本文主要是介绍【算法导论】排序 （四）：决策树、线性时间排序(计数、基数、桶排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
到目前为止，一共整理总结了五大排序算法：
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，即该元素出现的次数加1for(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)。线性排序算法使用最重要的是，充分利用数据特殊的性质，以达到最佳效果
终于把算法导论的八大排序总结完了。一共四篇，共四天时间。最后这一篇花的时间是最久的，其次是上一篇快速排序。 总结学过的知识，是一件很有趣的过程，并且经过总结，才发现了自己还有很多地方不懂，。
马上就期末各种考试 + 英语四级了， 算法的学习将会暂停一段时间。如果在期末考试之前还能抽出时间， 把《算法导论》前两部分的最后一章“中位数和顺序统计学”再整理总结出来，这一章也和排序有很大的关系，并且也很有意思。
—— 生命的意义，在于赋予它意义。
这篇关于【算法导论】排序 （四）：决策树、线性时间排序(计数、基数、桶排序)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
