排序算法:基数排序

前文

依旧闲来无事,随便划一下水,看到一个基数排序,挺有意思,在这做个记录

开始

之前也看断断续续写了很多代码,玩了很多有趣的东西,但是都没有留下任何记录,包括但 不限于用pyhton写的爬虫,爬的妹子图,爬的疾病分类,以及借助于第三方的插件,实现简单的微信群发功能,当然也有一些类似的排序,还有一些新技术的探索,平常写了也就写了,代码是不值钱的,基本上写了就不管了,所以也有很多代码遗失,想想还挺可惜,所以现在写了啥,都要做个记录,养成习惯。

正文

开局一张图,过程全靠编,看一张图吧,挺好理解的!

这张图什么意思呢?

就是下面的0-9就相当于桶,然后按照数字的个位十位百位来依次放入对应的桶中,然后循环最大的数的长度,然后反复来几次,就排序成功,挺简单

是什么?

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

上述一段话,来源于百度百科,其实很好理解,看图就知道了,0-9可以理解为桶,然后将每个数的单独位数的值循环计数排序,最后一次排序成功

基数排序有两种方法:1、LSD 最低位优先即从数字的右边开始 。2、MSD 最高位优先从最左边开始

算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/***
* 基数排序
*/
public static void radixSort(){
int[] array = {12, 33, 1, 4,543, 2, 444, 12};
int max = array[0];

//找到数组中的最大值 需要判断最大的数是多少位
for(int i=0;i<array.length;i++){
if(array[i]>max){
max = array[i];
}
}

//取到最大数的长度,用maxLen存着
int maxLen = 0;
while(max>0){
max /= 10;
maxLen++;
}

//buckets 为桶 外面的list存放 0-9个桶,每个桶里面装当前排序的数字
List<List<Integer>> buckets = new ArrayList<>();
//0-9十个数 new 十个桶
for(int i=0;i<10;i++){
//桶由ArrayList<Integer>构成
buckets.add(new ArrayList<>());
}

//按照数组里面最大的数的长度去循环,个,十,百,千,万。。。。等单独位数
for(int i=0;i<maxLen;i++){
//扫描所有数组元素,将元素按照每一位的大小分配到对应的桶中
for(int j=0;j<array.length;j++){
//取出一个数字上的第 i+1 位
//取余 12%10=2 234%100=34 次方 Math.pow(a,b) a的b次方
// 例:取个位 543%10=3 3/0=3 取十位 543%100=43 43/10=4
int key =array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);

//将取出来的数字先获取到该桶的位置,然后将数组中对应的值放到该桶中
buckets.get(key).add(array[j]);
}

//分配完之后 将桶中的数据拿出来,放到数组中排序
//数组索引
int counter = 0;
for(int j=0;j<10;j++){
//遍历0-9的桶
List<Integer> bucket =buckets.get(j);
//将桶里面的数据拿出来 遍历到数组里面
while(bucket.size()>0){
//将桶中的第一个元素复制到数组,并移除
array[counter++] = bucket.remove(0);
}
}
System.out.print("第"+(i+1)+"轮排序:");
for(int o : array){
System.out.print(o+" ");
}
}

}

先按照循环来说

1、第一个循环就是将数组里面最大的值找出来

2、第二个循环是按照最大的数字计算出数字的长度有多少位

3、使用List初始化桶

4、外面的循环是需要按照最大的数的长度来遍历

​ 1、这个循环最重要,取出每个数位上面的数字来放入对应的桶中

​ 上面代码中的注释有取出的方法

​ 2、这个循环是取出每个桶中对应的值,然后将这些值放到原数组中

上述就是这个代码,主要看图

引申

这个不能排负数,和字母,如果需要排字母,可以获取到字母的ASCII码,在排序ASCII码就好了,因为字母的顺序和它ASCII码的顺序是一一对应的

-------------本文结束感谢您的阅读-------------
0%