一、前言
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
二、算法思想
基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
算法步骤：
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
- 从最低位开始，依次进行一次排序。
- 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。
不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以 0~9 来表示的，所以我们不妨把 0~9 视为 10 个桶。
我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。
分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。
按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。
动态效果示意图：
1、代码
C++：
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | #include <iostream> #include <vector> using namespace std; // 求出数组中最大数的位数的函数 int MaxBit(vector<int> input){ // 数组最大值 int max_data = input[0]; for (int i = 1; i < input.size(); i++){ if (input[i] > max_data){ max_data = input[i]; } } // 数组最大值的位数 int bits_num = 0; while (max_data){ bits_num++; max_data /= 10; } return bits_num; } // 取数xxx上的第d位数字 int digit(int num, int d){ int pow = 1; while (--d > 0){ pow *= 10; } return num / pow % 10; } // 基数排序 vector<int> RadixSort(vector<int> input, int n){ // 临时数组，用来存放排序过程中的数据 vector<int> bucket(n); // 位记数器，从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个...是9的有多少个数 vector<int> count(10); // 从低位往高位循环 for (int d = 1; d <= MaxBit(input); d++){ // 计数器清0 for (int i = 0; i < 10; i++){ count[i] = 0; } // 统计各个桶中的个数 for (int i = 0; i < n; i++){ count[digit(input[i],d)]++; } /* * 比如某次经过上面统计后结果为：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]则经过下面计算后 结果为： [0, 2, * 5, 8, 8, 8, 8, 8, 8, 8]但实质上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中 * 非零数才用到，因为其他位不存在，它们分别表示如下：2表示比较位为1的元素可以存放在索引为1、0的 * 位置，5表示比较位为2的元素可以存放在4、3、2三个(5-2=3)位置，8表示比较位为3的元素可以存放在 * 7、6、5三个(8-5=3)位置 */ for (int i = 1; i < 10; i++){ count[i] += count[i - 1]; } /* * 注，这里只能从数组后往前循环，因为排序时还需保持以前的已排序好的顺序，不应该打 * 乱原来已排好的序，如果从前往后处理，则会把原来在前面会摆到后面去，因为在处理某个 * 元素的位置时，位记数器是从大到到小（count[digit(arr[i], d)]--）的方式来处 * 理的，即先存放索引大的元素，再存放索引小的元素，所以需从最后一个元素开始处理。 * 如有这样的一个序列[212,213,312]，如果按照从第一个元素开始循环的话，经过第一轮 * 后（个位）排序后，得到这样一个序列[312,212,213]，第一次好像没什么问题，但问题会 * 从第二轮开始出现，第二轮排序后，会得到[213,212,312]，这样个位为3的元素本应该 * 放在最后，但经过第二轮后却排在了前面了，所以出现了问题 */ for (int i = n - 1; i >= 0; i--){ int k = digit(input[i], d); bucket[count[k] - 1] = input[i]; count[k]--; } // 临时数组复制到 input 中 for (int i = 0; i < n; i++){ input[i] = bucket[i]; } } return input; } void main(){ int arr[] = { 50, 123, 543, 187, 49, 30, 0, 2, 11, 100 }; vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0])); cout << "排序前:"; for (int i = 0; i < test.size(); i++){ cout << test[i] << " "; } cout << endl; vector<int> result = test; result = RadixSort(result, result.size()); cout << "排序后:"; for (int i = 0; i < result.size(); i++){ cout << result[i] << " "; } cout << endl; system("pause"); } |
运行结果如下图所示：
Python：
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | # -*- coding:utf-8 -*- def RadixSort(input_list): ''' 函数说明:基数排序（升序） Author: www.cuijiahua.com Parameters: input_list - 待排序列表 Returns: sorted_list - 升序排序好的列表 ''' def MaxBit(input_list): ''' 函数说明:求出数组中最大数的位数的函数 Author: www.cuijiahua.com Parameters: input_list - 待排序列表 Returns: bits-num - 位数 ''' max_data = max(input_list) bits_num = 0 while max_data: bits_num += 1 max_data //= 10 return bits_num def digit(num, d): ''' 函数说明:取数xxx上的第d位数字 Author: www.cuijiahua.com Parameters: num - 待操作的数 d - 第d位的数 Returns: 取数结果 ''' p = 1 while d > 1: d -= 1 p *= 10 return num // p % 10 if len(input_list) == 0: return [] sorted_list = input_list length = len(sorted_list) bucket = [0] * length for d in range(1, MaxBit(sorted_list) + 1): count = [0] * 10 for i in range(0, length): count[digit(sorted_list[i], d)] += 1 for i in range(1, 10): count[i] += count[i - 1] for i in range(0, length)[::-1]: k = digit(sorted_list[i], d) bucket[count[k] - 1] = sorted_list[i] count[k] -= 1 for i in range(0, length): sorted_list[i] = bucket[i] return sorted_list if __name__ == '__main__': input_list = [50, 123, 543, 187, 49, 30, 0, 2, 11, 100] print('排序前:', input_list) sorted_list = RadixSort(input_list) print('排序后:', sorted_list) |
三、算法分析
1、基数排序的性能
其中，d代表数组元素最高为位数，n代表元素个数。
2、时间复杂度
这个时间复杂度比较好计算：count * length；其中 count 为数组元素最高位数，length为元素个数；所以时间复杂度：O(n * d)
3、空间复杂度
空间复杂度是使用了两个临时的数组：10 + length；所以空间复杂度：O（n）。
4、算法稳定性
在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。
本站整理自：
http://www.cnblogs.com/jingmoxukong/p/4311237.html
https://www.cnblogs.com/chunguang/p/5892768.html
2018年2月6日 下午1:57 沙发
python算法里第60行，循环条件 for i in range(1,length):应该是for i in range(1,10):
count列表只有10个元素，因为你的待排序序列刚好有十个数，所以程序没报错。待排序序列超过十个会下标溢出，少于十个排序错误。
2018年2月6日 下午2:06 1层
@zyh 感谢已更正~
2018年4月17日 下午4:27 板凳
python 第42行 判断条件 d>0 应该改成d>1，你可以试一下，输入列表稍微大一点，就不对了
2018年4月17日 下午4:52 1层
@hello 感谢指正，已更新。
2018年8月23日 下午4:32 地板
大神，for (int i = 1; i < 10; i++){
count[i] += count[i – 1];
} 请问这里对count数组做这样的处理是为什么？
2018年8月24日 上午9:37 1层
@yangdaotamu 有注释了啊，你思考下。举个例子。