【数据结构】排序算法---基数排序（动图演示）_msd基数排序

文章目录

• 1. 定义
• 2. 算法步骤
• • 2.1 MSD基数排序
  • 2.2 LSD基数排序
• 3. LSD 基数排序动图演示
• 4. 性质
• 5. 算法分析
• 6. 代码实现
• • C语言
  • Python
  • Java
  • C++
  • Go
• 结语

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

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 ( k n + ∑ i = 1 k w i ) O(kn+{\\sum_{i=1}^k}wi) O(kn+∑i=1k​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#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 SHOWPASS printf(\"\\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-8def radix_sort(array): max_num = max(array) place = 1 while max_num >= 10**place: place += 1 for i in range(place): buckets = [[] for _ in range(10)] for num in array: radix = int(num/(10**i) % 10) buckets[radix].append(num) j = 0 for k in range(10): for num in buckets[k]: array[j] = num j += 1 return array if __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 { @Override public 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 overflow maxData /= 10; ++d; } return d;/* int d = 1; //保存最大的位数 int p = 10; for(int i = 0; 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