学习心得--基数排序
基数排序(桶排序)介绍:
●1)
基数排序
（
radix sort
）属于“分配式排序”（
distribution sort
），又称“桶子法”（
bucket sort
）或
bin sort
，顾名思义，它是通过键值的各个位的值，将要排序的
元素分配
至某些“桶”中，达到排序的作用
●2)
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
●3)
基数排序
(Radix Sort)
是
桶排序
的扩展
●4)
基数排序是
1887
年赫尔曼
·
何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
基数排序基本思想
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序图文说明
第1轮排序 [按照个位排序]:
说明： 事先准备10个数组(10个桶)， 0-9 分别对应 位数的 0-9
(1) 将 各个数，按照个位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出
第2轮排序 [按照十位排序]
(1) 将 各个数，按照十位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出
第3轮排序 [按照百位排序]
(1) 将 各个数，按照百位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出
代码实现
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int[] arr = {53,3,542,748,14,214};
radixSort(arr);
}
public static void radixSort(int[] arr){
//得到数组中的最大的数的位数
int max = arr[0];//假设第一个数为最大数
for (int i = 1; i < arr.length; i++){
if (arr[i] > max)
max = arr[i];
}
int maxLength = (max+"").length();
//定义一个二维数组，表示10个桶，每个桶就是一个一维数组
int[][] bucket = new int[10][arr.length];
//为了记录每个桶中，实际放了多少数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
//bucketElementsCountsp[0],记录的就是bucket[0]桶的放入数据个数
int[] bucketElementsCounts = new int[10];
//第一轮（针对每个元素的个位进行排序处理）
for (int j = 0 ; j
运行结果：
基数排序的说明:
1)
基数排序是对传统桶排序的扩展，速度很快
.
2)
基数排序是经典的空间换时间的方式，占用内存很大,
当对海量数据排序时，容易造成
OutOfMemoryError
。
3)
基数排序是稳定的。
[
注
:
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
r[
i
]=r[j]
，且
r[
i
]
在
r[j]
之前，而在排序后的序列中，
r[
i
]
仍在
r[j]
之前，
则称这种排序算法是稳定的；否则称为不稳定的
]
4)
有负数的数组，我们不用基数排序来进行排序
,
如果要支持负数，
我的理解是将负数单独抽出来进行排序；
