10.2 表排序
10.2.1 算法概述
什么时候会用到表排序：
- 待排元素不是一个简单的整数，而是一个庞大的结构(比如说是一本书)
- 表排序在实际上是不需要移动原始数据的，移动的是指向他们位置的指针
间接排序：
- 不移动元素本身，只移动指针
- 定义一个指针数组作为"表"(table)
网络异常，图片无法展示|
- 交换的只是table的整数(指针)，得到
网络异常，图片无法展示|
10.2.2 物理排序
N个数字的排列由若干个独立的环组成，意思如下：
如何判断一个环的结束？每访问一个空位i后，就令table[i]=i。当发现table[i]==i时，环就结束了。
复杂度分析：
- 最好情况：初始即有序
- 物理排序过程的最坏情况是：有N/2个环，每个环包含2个元素。需要3N/2次元素移动
- T = O(mN),m是每个A元素的复制时间
10.3 基数排序
仅仅基于比较进行的排序所有的这些算法他的最坏时间复杂度下界是O(NlogN),也就是说不管有多快我们总能制造出一个最坏的情况让他用最快的算法跑他也只能跑到NlogN。
这个时候除了比较之外有没有更快的排序呢？有，那就是基数排序
10.3.1 桶排序
基数排序是桶排序的升级版
count是数组，这个数组的每一个元素都是一个指针，一开始被初始化为空链表的头指针，所以一开始有101个空链表(对应了101个空的桶 )
假设一个学生考88分：先找到88这个桶，然后把学生信息插到这个链表的表头里
伪码描述
voidBucket_Sort(ElementTypeA[],intN)
{
count[]初始化;
while(读入一个学生成绩grade)
将该生插入count[grade]链表;
for( i=0;i<M;i++){
if( count[i] )//桶不为空
输出整个count[i]链表;
}
}
桶排序算法的时间复杂度T(M, N)是多少？ T(N,M) =O(M+N)
当M非常小的时候(例如4w个学生只有101个不同成绩值，那这个时候其实就相当于一种线性的算法)
10.3.2 基数排序
如果M>>N的话怎么办？
值是0-999之间，最多一共就三位数。我们在考虑三位数的时候每一位数只有十种可能。
基数就是这个进制的基数，二进制的基数就是2，八进制基数就是8，所以十进制的基数自然就是10
输入序列：64，8，216，512，27，729，0，1，343，125
用"次位优先"(LeastSignificantDigit)=>简称LSD算法
//什么是次位优先？假设目前手里是216，这个时候6 个位数是最次位，2 百位数是主位(有一种算法是主位优先)
//比较先从个位数开始
第一步：建立十个桶
第二步：根据个位数把他们放入相应的桶里面
第三步：根据十位数放入相应的桶里面：
最后一步：根据百位数放入相应的桶里面：
设元素个数为N，整数进制为B，LSD的趟数为P，则最坏时间复杂度是：T=O(P(N+B))
次位优先LSD算法
对于给定范围在0-999之间的10个关键字{64，8，216，512，27，729，0，1，343，125}
① 先为最次位关键字建立桶（10个），将关键字按最次位分别放到10个桶中
② 然后将①中得到的序列按十位放到相应的桶里
③ 做一次收集，扫描每一个桶，收集到一个链表中串起来
④ 将③中得到的序列按最主位放到桶中
⑤ 最后做一次收集，这样就得到一个有序的序列了
10.3.3 多关键字的排序
基数排序不仅仅用于处理整数的基数，还可以用于处理有多关键字的排序
采用"主位优先"(MostSignificantDigit)排序：为花色建4个桶
在每个桶内分别排序，最后合并结果
=>其实我们还是需要在每个桶内调用相应的排序算法来解决，但是总体的时间复杂度会比我们把它完整的看成一个待排数组来排稍微好一点
采用"次位优先"(LeastSignificantDigit)排序：为面值建13个桶
这个方便就不需要再排序了，直接将结果合并，然后再为花色建4个桶就ok了
从上面两个例子来看，我们可以看出次位优先比主位优先要聪明得多，时间复杂度也快不少
10.4 排序算法的比较
前三个是简单排序，时间复杂度都是比较差的。优点在于程序非常好写，很短且不需要额外的空间
冒泡排序跟直接插入排序因为每次都交换两个相邻的元素，虽然慢，但是稳定
简单选择排序是跳着交换的，导致它是不稳定的
希尔排序是最先打破下界的算法，d最坏情况下是2，这个还是取决于增量排序，因为这是跳着排，所以也不稳定
堆排序跟归并排序理论来说，他们的时间复杂度都是最好的为NlogN
归并排序的缺点：需要一个额外的空间。当我们要排的数据量非常大的时候，归并排序会导致我们只能排一半的数据，本来可以排下的数据因为空间的问题而排不下。但好处在于稳定
