本部分的排序算法不基于比较，因此可以达到线性时间，而不受限于$\Omega(nlgn)$的时间界

1.计数排序

计数排序即Counting sort，其核心思想为：已知元素所处的范围后，将范围内所有可能取值全部设置一个位置(即一个数组)，然后将所有元素全部放入该数组，并同时累加得到各位置有几个元素；分散完成后计算前缀和即可得到各组相同元素所处的最后一个位置，总结起来为分散累加计数，前缀和计数排位

算法伪代码：
计数排序

算法分析

时间复杂度

算法时间复杂度为$\Theta (n+k)$，原因是：算法由几个循环构成，其中必然包含对$A$的遍历和$C$的遍历，故时间复杂度为$O(n+k)$。
另外计数排序需要$Theta (n+k)$的辅助空间，因此内存较大时可以使用该算法。

稳定性

计数排序是稳定的。但是如果修改最后遍历A数组的方向为从前往后,则不稳定,原因是C中存储的是相同元素中最后一个元素的位置。

2.基数排序

基数排序即Radix sort，算法核心思想为：将待排序的元素视作若干位k进制数字，然后从低位开始对每一位调用Couting sort作为子过程进行排序。由于计数排序时间复杂度随数字范围上升而上升，因此进制k的取值过大会导致每一轮时间变长；而k取值过小，会导致轮数过多，具体如何取值将在算法分析部分说明。

算法实现

算法分析

3.桶排序

桶排序即bucket sort，其核心思想为：对均匀分布的数据，先分散到排好序的、大小相同的桶里，然后在桶内进行插入排序。
由于数据均匀分布，因此各桶内元素不会过多(一般使用n个桶，和元素数量相同，因此桶内期望只有一个元素)，即先分段有序，再段内有序，并且分段有序是线性时间完成的，段内有序虽然是平方时间完成的但是是每一小段平方而非整个输入规模的平方，因此最终使得运行时间渐近趋近于$\Theta (n)$

算法实现

桶排序

算法分析

算法运行时间满足$T(n) = \Theta (n) + \sum_{i=1}^n O(n_i^2)$，其中$n_i$即各桶内元素数量，$\Theta (n)$代表将所有元素分散到桶内的时间。
而对于$n_i$，使用指示器变量来对其进行表示。指示器变量$X_{ij} = I{ A[j] \in B[i]}$，因此可将$n_i$表示如下：
\(\begin{aligned} n_i^2 &= (\sum_{j=1}^n X_{ij})^2 \\ &= \sum_{j=1}^n X_{ij} \sum_{k=1}^n X_{ik} \\ &= \sum_{j=1}^n X_{ij}^2 + \sum_{j=1}^n X_{ij} \sum_{k=1 \And k \neq j}^n X_{ik} \end{aligned}\)

取期望得到：
\(\begin{aligned} E(n_i^2) &= \sum_{j=1}^n E(X_{ij}^2) + E(\sum_{j=1}^n X_{ij} \sum_{k=1 \And k \neq j}^n X_{ik}) \\ &= \sum_{j=1}^n \frac{1}{n} + E(\sum_{j=1}^n \sum_{k=1 \And k \neq j}^n X_{ij}X_{ik}) \\ &= \sum_{j=1}^n \frac{1}{n} + \sum_{j=1}^n \sum_{k=1 \And k \neq j}^n E(X_{ij}X_{ik}) \end{aligned}\)

由于$j \neq k$时，$X_{ij},X_{ik}$独立，因此上式为：
\(\begin{aligned} E(n_i^2) &= \sum_{j=1}^n \frac{1}{n} + \sum_{j=1}^n \sum_{k=1 \And k \neq j}^n E(X_{ij}X_{ik}) \\ &= 1 + \sum_{j=1}^n \sum_{k=1 \And k \neq j}^n E(X_{ij})E(X_{ik}) \\ &= 1 + \sum_{j=1}^n \sum_{k=1 \And k \neq j}^n \frac{1}{n}\frac{1}{n} \\ &= 1+ n(n-1) \frac{1}{n^2} \\ &= 2-\frac{1}{n} \end{aligned}\)
综上，$T(n) = \Theta (n) + \sum_{i=1}^n O(2-\frac{1}{n}) = \Theta (n)$

算法拓展

此部分可参考《算法导论》习题8.4-4

只要各桶期望元素数量的平方和，即$\sum_{i=1}^n n_i^2$为$\Theta (n)$或至少为$O(n)$，那么对于非均匀分布，桶排序依然能在线性时间内完成排序。
本质：
简而言之，一种最简单情况，如果元素落在各桶的概率仍然为$\frac{1}{n}$，那么在推导过程中各指示器变量的期望都不会发生改变，也就是说推导过程完全不变，最终结论自然不变。当然，也有可能各桶概率不相等，但是最终元素数量平方和期望仍然为$O(n)$，这也是允许的，但不是最容易求解的情况。

对于各桶概率相等的情况，假设元素的分布函数为$f(x)$，那么对于任意一个桶区间$[b_i,b_{i+1}]$，必然有$\int_{b_i}^{b_{i+1}} f(x)dx = \frac{1}{n}$；然后可以从第一个桶，即$\int_{0}^{b_{1}} f(x)dx = \frac{1}{n}$开始依次求解桶的界限。

注意：根据这里的分析过程可以总结出在对某些期望分析时的技巧，即将随机变量变为指示变量的求和，从而对原随机变量的期望计算变为对指示变量的期望的求和，由于指示变量只有0,1两种取值，因此非常容易计算期望