说明
基数排序(radixsort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机(tabulation machine)上的
基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。LSD使用计数排序或桶排序,MSD可以使用桶排序。由低到高(LSD)比较简单,按位重排即可,如果是从高往低(MSD)则不能每次重排,可以通过递归来逐层遍历实现。详细请看各种不同版本的源码。
排序算法网上有很多实现,但经常有错误,也缺乏不同语言的比较。本系列把各种排序算法重新整理,用不同语言分别实现。
实现过程
将待排序数列(正整数)统一为同样的数位长度,数位较短的补零。
每个数位单独排序,从最低位到最高位,或从最高位到最低位。
这样从最低到高或从高到低排序完成以后,数列就变成一个有序数列。
示意图


性能分析
时间复杂度:O(k*N)
空间复杂度:O(k + N)
稳定性:稳定
代码
Java
class RadixSort {
// 基数排序,基于计数排序,按数位从低到高来排序
public static int[] countingSort(int arr[], int exponent) {
// 基数exponent按10进位,range为10
int range = 10;
int[] countList = new int[range];
int[] sortedList = new int[arr.length];
// 设定最小值以支持负数
int min = arr[0];
for (int i = 0; i = 0; i--) {
int item = arr[i] - min;
int idx = (item / exponent) % range;
// 根据计数位置得到顺序
sortedList[countList[idx] - 1] = arr[i];
countList[idx] -= 1;
}
// 最后赋值给原数据
for (int i = 0; i sortedList:" + Arrays.toString(sortedList));
return sortedList;
}
// 基数排序1,按数位大小,基于计数排序实现
public static int[] radixSort1(int arr[]) {
int max = arr[0];
for (int i = 0; i max) {
max = arr[i];
}
}
// 根据最大值,逐个按进位(基数)来应用排序,exponent即数位。
for (int exponent = 1; (max / exponent) > 0; exponent *= 10) {
countingSort(arr, exponent);
}
return arr;
}
}
// 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
// 1. 找出数组中最大的数,确定其位数。
// 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
// 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
// 重复步骤2和3,直到按照最高位排序完成。
class RadixSortMSD {
static int[] radixSort(int[] arr) {
int len = arr.length;
// 获取数组最大项
int max = arr[0];
for (int i = 0; i arr[i]) {
min = arr[i];
}
}
// 获取数字一共有几位,减去min得到最大值,以支持负数和减少最大值
int numberOfDigits = (int) (Math.log10(max - min) + 1);
int exponent = (int) (Math.pow(10, numberOfDigits - 1));
// 根据数组最大值,自后向前逐个按数位基数(exponent)比较排序。
return bucketSort(arr, len, exponent);
}
static int[] bucketSort(int[] arr, int len, int exponent) {
System.out.println("origin arr:" + Arrays.toString(arr) + " len=" + len + " exponent:" + exponent);
if (len arr[i]) {
min = arr[i];
}
}
// 位数按10递进
int range = 10;
// 定义桶二维数组,长度为10,放入0-9的数字
int[][] buckets = new int[range][len];
// 记录某个桶的最新长度,以便往桶内追加数据。
int[] bucketsCount = new int[range];
for (int i = 0; i 0 && bucketLen > 0) {
// 如果是数组且记录大于1则继续递归调用,位数降低1位
// 递归调用传参时需要传入当前子序列、子序列长度、当前分解的位数基数
int[] sortedBucket = bucketSort(bucket, bucketLen, (int) (exponent / range));
// 依照已排序的子序列实际长度,把各个桶里的值按顺序赋给原数组
for (int j = 0; j <h4>Python</h4><pre class="brush:py;">"""
基数排序LSD版,本基于桶排序。
1. 找出数组中最大的数,确定其位数。
2. LSD是低位到高位,依次按照位数的值将数字放入到不同桶中。
3. 按照桶顺序重新给数组排序。
重复步骤2和3,直到排序完成。
"""
def radix_sort(arr):
max_value = max(arr) # 找出数组中最大的数
min_value = min(arr) #最小值,为了支持负数
digit = 1 # 从个位开始排序
# 每次排序一个数位,从低到高直到排序完成
while (max_value - min_value) // digit > 0:
# 创建10个桶,分别对应0-9的数位值
buckets = [[] for _ in range(10)]
for num in arr:
# 找出当前位数的值
digit_num = (num - min_value) // digit % 10
# 将数字添加到对应数位的桶中,相当于根据数位排序
buckets[digit_num].append(num)
print('buckets:', buckets)
# 通过exend展开数组,相当于逐层添加
arr = []
for bucket in buckets:
arr.extend(bucket)
# 或逐项添加
# for item in bucket:
# arr.append(item)
# 数位移动到下一位
digit *= 10
return arr
"""
基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
1. 找出数组中最大的数,确定其位数。
2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
重复步骤2和3,直到按照最高位排序完成。
"""
# 桶排序,根据数位递归调用
def bucket_sort(arr, exponent):
print('origin arr:', arr, 'exponent:', exponent)
if (len(arr) <h4>Go</h4><pre class="brush:go;">// 2. 基数排序LSD版,计算最小值,基于计数排序实现
func radixSort2(arr []int) []int {
var arrLen = len(arr)
// 基数exponent按10进位,amount为10
var amount = 10
var sortedList = make([]int, arrLen)
var max = arr[0]
for i := 0; i max {
max = arr[i]
}
}
var min = arr[0]
for i := 0; i 0; exponent *= amount {
// 计数数组,长度为10,0-9一共10个数字
countList := make([]int, amount)
// 根据基数得到当前位数,并给计数数组对应位置加1
for i := 0; i countList:", countList)
// 根据计数数组按顺序取出排序内容
for i := arrLen - 1; i >= 0; i-- {
item := arr[i] - min
var idx = (item / exponent) % amount
sortedList[countList[idx]-1] = arr[i]
countList[idx] -= 1
}
// 将新顺序赋值给原数组
for i := 0; i <pre class="brush:go;">// 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
// 1. 找出数组中最大的数,确定其位数。
// 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
// 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
// 重复步骤2和3,直到按照最高位排序完成。
func radixSortMSD(arr []int) []int {
var amount = 10
maxValue := max(arr)
exponent := pow(amount, getNumberOfDigits(maxValue)-1)
bucketSort(arr, exponent)
return arr
}
func bucketSort(arr []int, exponent int) []int {
fmt.Println("origin arr:", arr, "exponent: ", exponent)
if exponent 0 {
numberOfDigits += 1
num /= 10
}
return numberOfDigits
}
// 获取绝对值
func abs(value int) int {
if value maxValue {
maxValue = arr[i]
}
}
return maxValue
}
// 计算数字次幂
func pow(a int, power int) int {
result := 1
for i := 0; i element {
minValue = element
}
}
return minValue
}
// 获取数字指定数位的值,超出数位补0,负数返回负数
// 如: 1024, 百位: 100 => 返回 0
// 如: -2048, 千位: 1000 => 返回 -2
func getDigit(arr []int, idx int, exponent int) int {
element := arr[idx]
digit := abs(element) / exponent % 10
if element <h4>JS</h4><pre class="brush:js;">// 基数排序2,从低到高逐个数位对比排序,基于桶排序,利用JS数组展开来还原数组
function radixSort2(arr) {
// 倒数获取数字指定位置的数
function getDigit(num, position) {
const digit = Math.floor(num / Math.pow(10, position - 1)) % 10
return digit
}
// 获取数组最大数字的位数
function getNumberLength(num) {
let maxLength = 0
while (num > 0) {
maxLength++
num /= 10
}
return maxLength
}
const max = Math.max.apply(null, arr)
const min = Math.min.apply(null, arr)
const maxLength = getNumberLength(max - min)
for (let i = 0; i [])
// 遍历数组将数位上的数放入对应桶里
for (let j = 0, l = arr.length; j <pre class="brush:js;">// 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
// 1. 找出数组中最大的数,确定其位数。
// 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
// 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
// 重复步骤2和3,直到按照最高位排序完成。
function radixSortMSD(arr) {
function bucketSort(arr, exponent) {
console.log('origin arr:', arr, 'exponent:', exponent)
if (!arr || arr.length 0) {
// 如果是数组则继续递归调用,位数降低1位
const sortedBucket = bucketSort(bucket, Math.floor(exponent / range))
// 把各个桶里的值按顺序赋给原数组
sortedBucket.forEach(num => {
arr[sortedIdx] = num
sortedIdx += 1
})
}
}
return arr
}
const max = Math.max.apply(null, arr)
const min = Math.min.apply(null, arr)
// 获取数字一共有几位,减去min得到最大值,以支持负数和减少最大值
const numberOfDigits = Math.floor(Math.log10(max - min) + 1)
const exponent = Math.pow(10, numberOfDigits - 1)
// 根据数组最大值,自后向前逐个按数位基数(exponent)比较排序。
return bucketSort(arr, exponent)
}
TS
class RadixSort {
// 基数排序,基于计数排序的基础上,按数字的每个位置来排序
countingSort(arr: Array<number>, exponent: number) {
const countList = Array<number>()
const range = 10
countList.length = range
countList.fill(0)
const min = Math.min.apply(null, arr)
for (let i = 0, l = arr.length; i ()
// 根据计数数组按顺序取出排序内容
for (let i = arr.length - 1; i >= 0; i--) {
const item = arr[i] - min
const idx = Math.floor((item / exponent) % range)
sortedList[countList[idx] - 1] = arr[i]
countList[idx] -= 1
}
// 最后赋值给原数据
for (let i = 0; i ) {
let sortedList = Array<number>()
const max = Math.max.apply(null, arr)
const min = Math.min.apply(null, arr)
for (
let exponent = 1;
Math.floor((max - min) / exponent) > 0;
exponent *= 10
) {
sortedList = this.countingSort(arr, exponent)
}
return sortedList
}
}</number></number></number>
C
// 计数排序,根据基数按位进行计数
void counting_sort(int arr[], int len, int exponent)
{
int sorted_list[len];
int range = 10;
int count_list[range];
// 找出最小值
int min_value = arr[0];
for (int i = 1; i = 0; i--)
{
int item = arr[i] - min_value;
int idx = (item / exponent) % range;
// 根据位置重排结果,减去min值还原数据
sorted_list[count_list[idx] - 1] = arr[i];
count_list[idx]--;
}
// 复制到数组重排原始数组
for (int i = 0; i max_value)
max_value = arr[i];
}
int min_value = arr[0];
for (int i = 1; i 0; exponent *= 10)
{
counting_sort(arr, len, exponent);
}
return arr;
}
// 根据最大长度来获取数字第n位的值,从前往后开始,前面不足最大长度时补零
int get_digit_by_position(int num, int position, int max_length)
{
if (num == 0)
{
return 0;
}
int number_length = (int)log10(num) + 1;
// 查询的位置加上自身长度不足最大长度则返回0
if ((position + number_length) 0)
{
digit = (num / exponent) % 10;
}
return digit;
}
// 基数排序,从高位到逐个对比排序,通过桶排序递归调用
// arr是数组,len是当前数组长度,position为自前往后的位置,max_length是最大值的数位
int *bucket_sort(int arr[], int len, int position, int max_length)
{
printf("\r\nlen=%d position=%d max_length=%d ", len, position, max_length);
if (len max_length)
{
return arr;
}
// 找出最小值
int min_value = arr[0];
for (int i = 1; i 0 && bucket_len > 0)
{
// 如果是数组且记录追加大于1则继续递归调用,位置增加1位
// 递归调用传参时需要传入当前子序列、子序列长度、当前分解的位数基数
int *sorted_bucket = bucket_sort(bucket, bucket_len, position + 1, max_length);
// 依照已排序的子序列实际长度,把各个桶里的值按顺序赋给原数组
for (int j = 0; j max_value)
max_value = arr[i];
}
// 获取最小项
int min_value = arr[0];
for (int i = 0; i arr[i])
{
min_value = arr[i];
}
}
// 获取数字一共有几位,减去min得到最大值,以支持负数和减少最大值
int max_length = (int)(log10(max_value - min_value) + 1);
// 根据数组最大值的长度,从前往后逐个对比排序。
return bucket_sort(arr, len, 1, max_length);
}
C++
// 基数排序,从个位到高位LSD版,基于计数排序实现
int *radixSort(int *arr, int len)
{
// 以10倍递进
int range = 10;
int sortedList[len];
int max = arr[0];
for (int i = 1; i max)
{
max = arr[i];
}
}
int min = arr[0];
for (int i = 1; i 0; exponent *= range)
{
// 计数数组,长度为10,0-9一共10个数字
int countList[range];
memset(countList, 0, range * sizeof(int));
// 根据基数得到当前位数,并给计数数组对应位置加1
for (int i = 0; i = 0; i--)
{
int item = arr[i] - min;
int idx = (item / exponent) % range;
sortedList[countList[idx] - 1] = arr[i];
countList[idx] -= 1;
}
// 复制输出数组到原始数组
for (int i = 0; i <h3>链接</h3><p>基数排序与计数排序、桶排序区别</p><p>基数排序与计数排序、桶排序三者概念很像,但也有不同,其主要差异如下:</p><p>计数排序:根据数组值设定若干个桶,每个桶对应一个数值,将这些桶的值分别存入下一个桶中用于排序,最后按顺序取出对应桶里的值。</p><p>桶排序:根据情况分为若干个桶,每个桶存储一定范围的数值,每个桶再单独排序,最后按桶的顺序取出全部数据。</p><p>基数排序:根据数据的位数来分配桶,每一位对应一个桶,先将全部数据的位数按最大位数对齐,再根据位数上的值大小排列。基数排序基于计数排序或者桶排序。</p>











