【数据结构】排序算法---基数排序

⚠本节要介绍的不是计数排序

1. 定义

基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。基数排序将待排序的元素拆分为k个关键字，逐一对各个关键字排序后完成对所有元素的排序。

• 如果是从第1关键字到第k关键字顺序进行比较，则该基数排序称为 MSD（Most Significant Digit first)基数排序——最高位优先法（从高位到低位）；

• 如果是从第k关键字到第1关键字顺序进行比较，则该基数排序称为 LSD（Least Significant Digit first)基数排序——最低位优先法（从低位到高位）。

基数排序是将整数按位数切割成不同的数字，然后按每个位数分别比较，由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

2. 算法步骤

2.1 MSD基数排序

将待排序的元素拆分为k个关键字，先对第1关键字进行稳定排序，然后对于每组 具有相同关键字的元素 再对第2关键字进行稳定排序（递归执行）……最后对于每组 具有相同关键字的元素 再对第k关键字进行稳定排序。

一般而言，我们默认基数排序是稳定的，所以在 MSD 基数排序中，我们也仅仅考虑借助 稳定算法（通常使用计数排序）完成内层对关键字的排序。

2.2 LSD基数排序

将待排序的元素拆分为k个关键字，然后先对 所有元素 的第k关键字进行稳定排序，再对 所有元素 的第k-1关键字进行稳定排序，再对 所有元素 的第k-2关键字进行稳定排序……最后对 所有元素 的第1关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

LSD 基数排序也需要借助一种 稳定算法 完成内层对关键字的排序。同样的，通常使用计数排序来完成。

3. LSD 基数排序动图演示

4. 性质

稳定性：

如果对内层关键字的排序是稳定的，则 MSD 基数排序和 LSD 基数排序都是稳定的排序算法。

空间复杂度：

MSD 基数排序和 LSD 基数排序的空间复杂度都为$O(k+n)$。

时间复杂度：

基数排序每一位的比较可以使用线性排序，比如桶排序或者计数排序，当然需要保证如计数排序的稳定性。每次排序时间复杂度O(n)，那么如果有k位，则时间复杂度为$O(k\ast n)$,如果k不大比如手机号11位，那么时间复杂度就是$O(n)$

通常而言，基数排序比基于比较的排序算法（比如快速排序）要快。但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择。

一般来说，如果每个关键字的值域都不大，就可以使用 [计数排序]作为内层排序，此时的复杂度为$O(kn+{\sum }_{i=1}^{k}wi)$，其中$wi$为第i关键字的值域大小。如果关键字值域很大，就可以直接使用基于比较的$O(nklogn)$排序而无需使用基数排序了。

5. 算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要$O(n)$的时间复杂度，而且分配之后得到新的关键字序列又需要$O(n)$的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是$O(d\ast 2n)$，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说$n>>k$，因此额外空间需要大概n个左右。

6. 代码实现

C语言

#include<stdio.h>
#define MAX 20
//#define SHOWPASS
#define BASE 10void print(int *a, int n) {int i;for (i = 0; i < n; i++) {printf("%d\t", a[i]);}
}void radixsort(int *a, int n) {int i, b[MAX], m = a[0], exp = 1;for (i = 1; i < n; i++) {if (a[i] > m) {m = a[i];}}while (m / exp > 0) {int bucket[BASE] = { 0 };for (i = 0; i < n; i++) {bucket[(a[i] / exp) % BASE]++;}for (i = 1; i < BASE; i++) {bucket[i] += bucket[i - 1];}for (i = n - 1; i >= 0; i--) {b[--bucket[(a[i] / exp) % BASE]] = a[i];}for (i = 0; i < n; i++) {a[i] = b[i];}exp *= BASE;#ifdef SHOWPASSprintf("\nPASS   : ");print(a, n);
#endif}
}int main() {int arr[MAX];int i, n;printf("Enter total elements (n <= %d) : ", MAX);scanf("%d", &n);n = n < MAX ? n : MAX;printf("Enter %d Elements : ", n);for (i = 0; i < n; i++) {scanf("%d", &arr[i]);}printf("\nARRAY  : ");print(&arr[0], n);radixsort(&arr[0], n);printf("\nSORTED : ");print(&arr[0], n);printf("\n");return 0;
}

Python

# coding=utf-8
def radix_sort(array):max_num = max(array)place = 1while max_num >= 10**place:place += 1for i in range(place):buckets = [[] for _ in range(10)]for num in array:radix = int(num/(10**i) % 10)buckets[radix].append(num)j = 0for k in range(10):for num in buckets[k]:array[j] = numj += 1return arrayif __name__ == '__main__':array = [25, 17, 33, 17, 22, 13, 32, 15, 9, 25, 27, 18]print(radix_sort(array))

Java

/*** 基数排序* 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9*/
public class RadixSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);int maxDigit = getMaxDigit(arr);return radixSort(arr, maxDigit);}/*** 获取最高位数*/private int getMaxDigit(int[] arr) {int maxValue = getMaxValue(arr);return getNumLenght(maxValue);}private int getMaxValue(int[] arr) {int maxValue = arr[0];for (int value : arr) {if (maxValue < value) {maxValue = value;}}return maxValue;}protected int getNumLenght(long num) {if (num == 0) {return 1;}int lenght = 0;for (long temp = num; temp != 0; temp /= 10) {lenght++;}return lenght;}private int[] radixSort(int[] arr, int maxDigit) {int mod = 10;int dev = 1;for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)int[][] counter = new int[mod * 2][0];for (int j = 0; j < arr.length; j++) {int bucket = ((arr[j] % mod) / dev) + mod;counter[bucket] = arrayAppend(counter[bucket], arr[j]);}int pos = 0;for (int[] bucket : counter) {for (int value : bucket) {arr[pos++] = value;}}}return arr;}/*** 自动扩容，并保存数据** @param arr* @param value*/private int[] arrayAppend(int[] arr, int value) {arr = Arrays.copyOf(arr, arr.length + 1);arr[arr.length - 1] = value;return arr;}
}

C++

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{int maxData = data[0];              ///< 最大数/// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。for (int i = 1; i < n; ++i){if (maxData < data[i])maxData = data[i];}int d = 1;int p = 10;while (maxData >= p){//p *= 10; // Maybe overflowmaxData /= 10;++d;}return d;
/*    int d = 1; //保存最大的位数int p = 10;for(int i = 0; i < n; ++i){while(data[i] >= p){p *= 10;++d;}}return d;*/
}
void radixsort(int data[], int n) //基数排序
{int d = maxbit(data, n);int *tmp = new int[n];int *count = new int[10]; //计数器int i, j, k;int radix = 1;for(i = 1; i <= d; i++) //进行d次排序{for(j = 0; j < 10; j++)count[j] = 0; //每次分配前清空计数器for(j = 0; j < n; j++){k = (data[j] / radix) % 10; //统计每个桶中的记录数count[k]++;}for(j = 1; j < 10; j++)count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中{k = (data[j] / radix) % 10;tmp[count[k] - 1] = data[j];count[k]--;}for(j = 0; j < n; j++) //将临时数组的内容复制到data中data[j] = tmp[j];radix = radix * 10;}delete []tmp;delete []count;
}

Go

var (K int = 3 // 基数排序需要的全局变量RADIX int = 10queue [][]int
)
func radix_sort_queue_pop(qu []int) []int {if len(qu) == 0 {return qu // 如果数组为空，不做任何操作}// 删除第一个元素qu = qu[1:]return qu
}
func radix_sort_queue_push(qu []int, data int) []int {qu = append(qu, data)return qu
}
func radix_sort_get_key(value int, k int) int {key := 0for k >= 0 {key = value % 10value /= 10k--}return key
}
func radix_sort_distribute(arr []int, left int, right int, k int){// k表示是第几次分发数据for i:=left; i<right; i++ {key := radix_sort_get_key(arr[i], k)queue[key] = radix_sort_queue_push(queue[key], arr[i])}
}
func radix_sort_collect(arr []int) {k := 0for i:=0; i < RADIX; i++ {for len(queue[i]) != 0 {arr[k] = queue[i][0] // 先进先出k++queue[i] = radix_sort_queue_pop(queue[i])}}
}
func radix_sort_by_group(arr []int, left int, right int) {for i:=0; i<K; i++ {// 分发数据radix_sort_distribute(arr, left, right, i)// 回收数据radix_sort_collect(arr)}
}
func radix_sort(arr []int, sz int) {// 初始化队列queue = make([][]int, RADIX)left := 0right := sz;radix_sort_by_group(arr, left, right)
}

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！

带你初步了解排序算法：https://blog.csdn.net/2301_80191662/article/details/142211265
直接插入排序：https://blog.csdn.net/2301_80191662/article/details/142300973
希尔排序：https://blog.csdn.net/2301_80191662/article/details/142302553
直接选择排序：https://blog.csdn.net/2301_80191662/article/details/142312028
堆排序：https://blog.csdn.net/2301_80191662/article/details/142312338
冒泡排序：https://blog.csdn.net/2301_80191662/article/details/142324131
快速排序：https://blog.csdn.net/2301_80191662/article/details/142324307
归并排序：https://blog.csdn.net/2301_80191662/article/details/142350640
计数排序：https://blog.csdn.net/2301_80191662/article/details/142350741
桶排序：https://blog.csdn.net/2301_80191662/article/details/142375338
基数排序：https://blog.csdn.net/2301_80191662/article/details/142375592
十大经典排序算法总结与分析：https://blog.csdn.net/2301_80191662/article/details/142211564