算法导论（线性时间排序）算法导论：线性时间排序

线性时间排序
对于比较排序来说，在排序的最终结果中，各元素的次序依赖于它们之间的比较。我们可以看到下图中的比较排序算法，在最坏情况下情况下，时间复杂度至少O(nlgn)。

文章图片
线性时间排序
从图中我们可以较为清楚的看到各算法的时间复杂度，下面将证明对包含n个元素的输入序列来说，在最坏情况下，时间复杂度至少都是O(nlgn)。

文章图片
决策树
比较排序可以被抽象为一颗决策树，那什么是决策树呢？比如上图所示，现在要出去相亲，首先判断年龄，如果大于30岁，那就直接不见了，小于30再考虑其他条件。之后，我们依次判断了，长相，收入，都满足了要求，于是决定去见上一面。
决策树是一颗完全二叉树（美式定义：要么有左右孩子、要么就没有孩子），非叶子结点都是一个逻辑判断，每个分支都是判断结果。
文章图片
决策树
如上图所示，现在有三个数x,y,z。我们可以构建出如图所示的决策树，根结点是x和y比较，如果x≤y，再比较y和z的大小，如果x≥y，则比较x和z的大小。这里有三个数，并且是互异的，所以大小排列情况会有6种，如果有n个互译的数，那就是n!种。当x=6，y=8，z=5时，最后就会得到这个结果，也就是<5,6,8>。

算法导论（线性时间排序）
文章图片
决策树
在最坏情况下，比较的次数，就是树的高度，2的h次方表示的是，总共的结点，肯定比叶子结点多，最后可以解出，h是大于等于O(nlgn)的。
介绍完了比较排序的时间复杂度，现在该介绍线性时间排序了。
计数排序

问题描述：给定一个无序的序列，对序列进行排序，使之成为有序。基本思想：对于每一个输入元素x，确定小于x的元素个数，可以直接把x放到它在输出数组中的位置上,但是需要略微修改，因为一个位置不能存放两个元素

算法的主要思想就是找到比元素x小的元素个数，元素x是待排序的元素。
那这个排序过程如何实现的呢？

文章图片
计数排序
A数组就是我们的待排序序列{2，5，3，0，2，3，0，3}，C数组是用来记录比元素x小的元素个数，因为A中的数是0-5，所以B中的数组大小也是0~5，上标表示的就是A中的数。

文章图片
计数排序
我们现在先记录，每个元素的个数是多少，现在指向2所以2的个数标记为1。

文章图片
计数排序
指向5，所以5的个数变为1。

文章图片
计数排序
在完成后，数组C中记录下了，各元素的个数。不过我们最终要的结果是记录下比元素x小的元素个数，所以这里面的数字还要进行简单的变换。

文章图片
计数排序
现在我们将1中的0变更为2，这个数字表示的是小于等于1的数，也就是2，下面我们再记录小于等于2的数。

文章图片
计数排序
小于等于2的个数，就是前面小于等于1的个数，再加上2自身的个数，结果为4。

文章图片
计数排序
在完成更新后，所得如上图所示，每个数组中记录的数，就是小于等于自身的元素的个数。

文章图片
排序
B数组就是我们最后的排序结果，对A数组从右向左进行遍历，这样是为了让排序是稳定的，排序的稳定是指，对于相同的数字，比如这里的2，在排序完成后，并不改变它们的相对次序。

文章图片
计数排序
这里我们对3进行排序，去B数组查找，小于等于3的个数，找到为7就直接放在上标为7的数组中，并且将B中记录的数字减1。

文章图片
计数排序
排序完成的结果，如图所示。

文章图片
计数排序时间复杂度
因为要遍历两遍A数组，以及遍历一遍B数组，所以时间复杂度为O(n)+O(n)+O(k)=O(k+n)，当k=O(n)时T(n)=O(n)。基数排序

基本思想：基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，实质是多关键字排序。注意事项：选择低位优先排序，因为如果按照高位优先排序的，当排到次高位时，还需要返回看高位数字,相对来说比较麻烦。

文章图片
基数排序
例如，现在给出了7个数字，我们要对其进行排序，在这种位数很多的情况下，我们优先选择的就是基数排序。在基数排序时，优先对个位数进行排序，也就是最右边的那位数。

文章图片
基数排序
要对个位数数字进行排序，那选择什么样的方法对其进行排序呢？只要是线性时间的排序，都是可行的，这里我们选择之前讲过的计数排序。

文章图片
基数排序
再对十位数上面的数字进行排序。

文章图片
基数排序
在完成排序后，可以得到上图的结果。
时间复杂度分析：
每个数字都是d位数，比如说这里都是三位数。每一次排序，都是计数排序，时间复杂度为O(n+k)，总共d次计数排序。所以时间复杂度为O(n+k) d=O(d(n+k))。
桶排序一般来说，只有在输入数据是给定的一个范围内，并且还是服从均匀分布的，才会使用桶排序。