数据结构算法介绍之基数排序(Radix Sort)

一、基数排序算法简介

讯享网

（1）概念：基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序是非比较型整数排序算法，其原理是将整数按位分割进行排序。基数排序适用于大范围数据排序，打破了计数排序的限制。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

（2）2种排序方式：

最低位优先法(LSD)：从最低位向最高位依次按位进行排序。

最高位优先法(MSD)：从最高位向最低位依次按位进行排序。

（3）按位分割小技巧

arr[i] / digit % 10，其中digit为10^n。

总结：

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

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

二、基数排序算法示意图：

三、基数排序算法代码展示：

C语言代码：

#include<math.h> testBS() { inta[] = {2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3}; int *a_p = a; //计算数组长度 intsize = sizeof(a) / sizeof(int); //基数排序 bucketSort3(a_p, size); //打印排序后结果 inti; for(i = 0; i < size; i++) { printf("%d\n", a[i]); } intt; scanf("%d", t); } //基数排序 voidbucketSort3(int *p, intn) { //获取数组中的最大数 intmaxNum = findMaxNum(p, n); //获取最大数的位数，次数也是再分配的次数。 intloopTimes = getLoopTimes(maxNum); inti; //对每一位进行桶分配 for(i = 1; i <= loopTimes; i++) { sort2(p, n, i); } } //获取数字的位数 intgetLoopTimes(intnum) { intcount = 1; inttemp = num / 10; while(temp != 0) { count++; temp = temp / 10; } returncount; } //查询数组中的最大数 intfindMaxNum(int *p, intn) { inti; intmax = 0; for(i = 0; i < n; i++) { if(*(p + i) > max) { max = *(p + i); } } returnmax; } //将数字分配到各自的桶中，然后按照桶的顺序输出排序结果 voidsort2(int *p, intn, intloop) { //建立一组桶此处的20是预设的根据实际数情况修改 intbuckets[10][20] = {}; //求桶的index的除数 //如798个位桶index=(798/1)%10=8 //十位桶index=(798/10)%10=9 //百位桶index=(798/100)%10=7 //tempNum为上式中的1、10、100 inttempNum = (int)pow(10, loop - 1); inti, j; for(i = 0; i < n; i++) { introw_index = (*(p + i) / tempNum) % 10; for(j = 0; j < 20; j++) { if(buckets[row_index][j] == NULL) { buckets[row_index][j] = *(p + i); break; } } } //将桶中的数，倒回到原有数组中 intk = 0; for(i = 0; i < 10; i++) { for(j = 0; j < 20; j++) { if(buckets[i][j] != NULL) { *(p + k) = buckets[i][j]; buckets[i][j] = NULL; k++; } } } }

JAVA语言：

讯享网public class RadixSort { public static void sort(int[] number, int d) //d表示最大的数有多少位 { intk = 0; intn = 1; intm = 1; //控制键值排序依据在哪一位 int[][]temp = newint[10][number.length]; //数组的第一维表示可能的余数0-9 int[]order = newint[10]; //数组order[i]用来表示该位是i的数的个数 while(m <= d) { for(inti = 0; i < number.length; i++) { intlsd = ((number[i] / n) % 10); temp[lsd][order[lsd]] = number[i]; order[lsd]++; } for(inti = 0; i < 10; i++) { if(order[i] != 0) for(intj = 0; j < order[i]; j++) { number[k] = temp[i][j]; k++; } order[i] = 0; } n *= 10; k = 0; m++; } } public static void main(String[] args) { int[]data = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100}; RadixSort.sort(data, 3); for(inti = 0; i < data.length; i++) { System.out.print(data[i] + ""); } } }

Python语言：

#!/usr/bin/env python #encoding=utf-8 import math def sort(a, radix=10): """a为整数列表， radix为基数""" K = int(math.ceil(math.log(max(a), radix))) # 用K位数可表示任意整数 bucket = [[] for i in range(radix)] # 不能用 [[]]*radix for i in range(1, K+1): # K次循环 for val in a: bucket[val%(radixi)/(radix(i-1))].append(val) # 析取整数第K位数字 （从低到高） del a[:] for each in bucket: a.extend(each) # 桶合并 bucket = [[] for i in range(radix)]

四、基数排序算法性能分析：

 时间效率 [1]  ：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。