内容来自尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili

写在前面:本文内容大致和原视频内老师的笔记内容相同，会偶尔插入自己的注释和理解，尽量会完成作业

7.11基数排序

7.11.1基数排序(桶排序)介绍:

1.      基数排序(radix sort)属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort)或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用

2.      基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法

3.      基数排序(Radix Sort)是桶排序的扩展

4.      基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字，然后按每个位数分别比较。

7.11.2基数排序的基本思想

1.      将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

2.      这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤

7.11.3基数排序的图文说明

将数组{53,3,542,748,14,214}使用基数排序，进行升序排序

第一轮排序：

7.11..4基数排序代码实现

将数组{53,3,542,748,14,214}使用基数排序，进行升序排序

1.     思路分析：前面图文已经讲明确

2.     代码实现

7.11.5基数排序的说明

1.     基数排序是对传统桶排序的扩展，速度很快.

2.     基数排序是经典的空间换时间的方式，占用内存很大，当对海量数据排序时，容易造成OutOfMemoryError 。

3.     基数排序是稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的;否则称为不稳定的]

4.     有负数的数组，我们不用基数排序来进行排序,如果要支持负数，参考:

https://code.i-harness.com/zh-CN/q/e98fa9

这个网页里面的内容如下：

sorting - sort翻译 - 基数排序维基百科

基数排序为负整数 (4)

我正在尝试实现基数整数，包括负整数。 对于非负整数，我打算创建一个相应的10个队列的队列0-9，并实现LSD算法。 但是我对负面的整数感到困惑。 我现在的想法是继续为他们创建10个队列，分别排序，最后给出2个列表，其中一个包含负整数，另一个包含非负整数。 最后我会合并它们。

你怎么看待这件事？ 是否有更有效的方法来处理负整数？

谢谢！

另外一个解决方案是将数组中的负数整数分开，使它们成为正数，然后使用基数排序为正值，然后反转并附加排序后的非负数组。

您可以将标志视为一种特殊的数字。 你把单位堆，然后十等，最后在标志上。 这确实会为底片产生相反的顺序，然后您只需反转该底片的内容即可。 这是多少年的机械卡分拣机工作。

请注意，符号位是有符号整数中的最高位，但默认情况下，所有数字均被基数排序为无符号整数。 所以你需要告诉算法负数小于正数。 在32位有符号整数的情况下，可以先排序三个低位字节，然后对符号位反转的第四个（高位）字节进行排序，这样0将用于负数而不是1，因此它们将首先排序。

我强烈建议按字节对数字进行排序，而不是用十进制数字，因为机器比提取数字要容易得多。

处理带符号值的最简单方法可能是在最重要的数字上进行操作时抵消积累的起始位置（即产生位置偏移）。 将所有数字转换为无符号数据也是一种选择，但要求对数组数组至少应用两次（一次准备输入，一次还原输出）。

这使用第一种技术以及字节大小的数字（字节访问通常更高效）：

原谅我不认识这个语言[s:ac:怕]