【数据结构笔记38】桶排序 基数排序 多关键字排序 排序算法汇总比较

本次笔记内容：

10.3.1 桶排序

10.3.2 基数排序

10.3.3 多关键字排序

10.4 排序算法比较

文章目录

排序算法背景

有定理证明：基于之前所介绍的排序方法，最坏情况下，时间复杂度最好也只有O(Nlog⁡2N)O(N \log_2 N)O(Nlog2​N)。

有没有可能更快？

桶排序

如上图，每一个数值都是一个“桶”，扫描学生数据时，遇到哪个值，就把这个学生的值插到该值对应的桶的链表头里。其时间复杂度是T(N,M)=O(M+N)T(N,M)=O(M+N)T(N,M)=O(M+N)。

上述例子中，N一般远大于M，是在线性时间内做排序。那么如果M很大怎么办？

基数排序

如上图，使用“次位优先”（LSD，Least Significant Digit）的基数排序。

首先安装各位进行“装桶”，之后安装十位、百位。每次装桶都放在该链表的末尾。最后一次装桶完成，则安装桶的顺序输出即可。

其时间复杂度是T=(O(P(N+B)))T=(O(P(N+B)))T=(O(P(N+B)))。每一趟排序中，遍历N个数，访问B个桶，一共P趟。

多关键字排序（基数排序）

如上图，使用“主位优先”（Most Significant Digit）排序，先为花色建立4个桶。

但是，在这种情况中，使用LSD排序更为聪明。

如上，如果使用LSD，则第一趟排序结束后，将扑克牌放到“花色”的桶中，无需排序。

排序算法的比较

各种排序算法特点如上图。