从低位到高位,每轮按位分组比较,将排序结果,在二维表与一维表中,来回倒换,最终实现稳定排序。

前置条件

1、限正整数

2、申请辅助二维表

0 1 2 3 4 5 6 7 8 9

最大数字,有多少位,就排序多少轮,从低位向高位,每轮排序1位,先个位排序所有数字,个位数等于几,就把数字放二维表某列中,多位相同的,就依次往后加,再十位排序,再百位……

排序前: [49 11 36 83 5 55 88 30 43 25 35 98 52 73 80 68 72 4]  

第1轮个位排序,表头表示个数,个位数和表头相同数字,存放在相应表头列中,如下:

0 1 2 3 4 5 6 7 8 9
30 11 52 83 4 5 36 88 49
80 72 43 55 98
73 25 68
35

将二维表中从0到9组合到一个队列中,[30 80 11 52 72 83 43 73 4 5 55 25 35 36 88 98 68 49],为下轮排序做准备;
第2轮十位排序,二维表头表示十位,十位数和表头相同数字,存放在相应表头列中,如下:

0 1 2 3 4 5 6 7 8 9
4 11 25 30 43 52 68 72 80 98
5 35 49 55 73 83
36 88

将二维表中从0到9组合到一个队列中[4 5 11 25 30 35 36 43 49 52 55 68 72 73 80 83 88 98],

表中最大数字,是二位数,所以排序2轮;

//基数排序
func radixSort(nums []int) []int {
	//基数排序
	//  将数组按照位数分组
	//  对每一位数组进行排序
	//  将排序后的数组合并
	//  将每一位数组递归排序

	var max int
	for i, v := range nums {
		if i == 0 {
			max = v
			continue
		}
		if v > max {
			max = v
		}
	}

	//计算最大数的位数
	digit := 0
	for max > 0 {
		max /= 10
		digit++
	}

	//按照位数分组
	buckets := make([][]int, 10)

	for i := 0; i < digit; i++ {
		for i := 0; i < 10; i++ {
			buckets[i] = make([]int, 0) //初始化桶
		}
		for _, v := range nums {
			//按照位数分组
			buckets[v/int(math.Pow(10, float64(i)))%10] = append(buckets[v/int(math.Pow(10, float64(i)))%10], v)
		}
		fmt.Printf("第%d轮排序:%v\n", i+1, buckets)

		nums = make([]int, 0)
		for j := 0; j < 10; j++ {
			nums = append(nums, buckets[j]...)
			buckets[j] = make([]int, 0)
		}
	}

	return nums

}

测试结果

排序前:  [28638 79564 52285 87418 90363 94912 52373 22068 39239 31380 94505 43587 1985 56625 69561]
第1轮排序:[[31380] [69561] [94912] [90363 52373] [79564] [52285 94505 1985 56625] [] [43587] [28638 87418 22068] [39239]]
第2轮排序:[[94505] [94912 87418] [56625] [28638 39239] [] [] [69561 90363 79564 22068] [52373] [31380 52285 1985 43587] []]
第3轮排序:[[22068] [] [39239 52285] [90363 52373 31380] [87418] [94505 69561 79564 43587] [56625 28638] [] [] [94912 1985]]
第4轮排序:[[90363] [31380 1985] [22068 52285 52373] [43587] [94505 94912] [] [56625] [87418] [28638] [39239 69561 79564]]
第5轮排序:[[1985] [] [22068 28638] [31380 39239] [43587] [52285 52373 56625] [69561] [79564] [87418] [90363 94505 94912]]
排序后:  [1985 22068 28638 31380 39239 43587 52285 52373 56625 69561 79564 87418 90363 94505 94912]