内部排序——基数排序 and 总结

大家好，想要了解完整的内部排序可以看一下前面的文章。

5.基数排序

排序的一种内排序方法。根据在实际工程中使用的关键字大都是由数字(或字母)组成的，现在，以数字为例来说明这种排序的过程我们知道数字关键字都是由 0 到 9 一个数字组成，那么，在内存设立编号为 0-9 的十个桶。对待排序的记录从其关键字的最低位到最高位作如下处理:把每个记录存放(分配)到内存中桶号与该记录关键字当前数位上数字相同的桶中。经过处理(收集)得到一次排序结果。

下面以顺序存储为例看一看实际过程：

由上面分析可知基数排序若用顺序存储，每个桶都要分配 n 个单元总的空间量应为 10*n。作但实际上根本用不了那么多，因而造成空间的极大浪费。所以，基数排序一般都采用链表存储。链表存储的排序原理与顺序存储相同，不再论述，大家可以自己看。

内部排序总结

（建议小伙伴们看一下前面的文章）

这是对内部排序总结的脑图。

对各种排序方法时间上的比较

• 平均时间性能:快速排序→归并排序→堆排序→简单排序

• 简单程度:直接插入排序最简单。常与其他方法结合使用。

• 稳定性:快速排序、堆排序、希尔排序都是不稳定的。

• 基数排序最适用于 n 值很大而关键字车较小的序列。

以上就是对内部排序的总结，希望小伙伴可以在评论区讨论一下呦！