经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » Java相关 » Java » 查看文章
【基数排序算法详解】Java/Go/Python/JS/C不同语言实现
来源:cnblogs  作者:刀法如飞  时间:2023/3/6 9:20:11  对本文有异议

说明

基数排序(RadixSort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机(Tabulation Machine)上的贡献。

基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。LSD使用计数排序或桶排序,MSD可以使用桶排序。由低到高(LSD)比较简单,按位重排即可,如果是从高往低(MSD)则不能每次重排,可以通过递归来逐层遍历实现。详细请看各种不同版本的源码。

排序算法网上有很多实现,但经常有错误,也缺乏不同语言的比较。本系列把各种排序算法重新整理,用不同语言分别实现。

实现过程

  1. 将待排序数列(正整数)统一为同样的数位长度,数位较短的补零。
  2. 每个数位单独排序,从最低位到最高位,或从最高位到最低位。
  3. 这样从最低到高或从高到低排序完成以后,数列就变成一个有序数列。

 

示意图

 

 

性能分析

时间复杂度:O(k*N)
空间复杂度:O(k + N)
稳定性:稳定

 

代码

 

Java

  1. class RadixSort {
  2. // 基数排序,基于计数排序,按数位从低到高来排序
  3. public static int[] countingSort(int arr[], int exponent) {
  4. // 基数exponent按10进位,range为10
  5. int range = 10;
  6. int[] countList = new int[range];
  7. int[] sortedList = new int[arr.length];
  8. // 设定最小值以支持负数
  9. int min = arr[0];
  10. for (int i = 0; i < arr.length; i++) {
  11. if (arr[i] < min) {
  12. min = arr[i];
  13. }
  14. }
  15. // 根据基数求得当前项目对应位置的数值,并给对应计数数组位置加1
  16. for (int i = 0; i < arr.length; i++) {
  17. int item = arr[i] - min;
  18. // 根据exponent获得当前位置的数字是几,存入对应计数数组
  19. int idx = (item / exponent) % range;
  20. countList[idx] += 1;
  21. }
  22. // 根据位置计数,后面的位数为前面的累加之和
  23. for (int i = 1; i < range; i++) {
  24. countList[i] += countList[i - 1];
  25. }
  26. System.out.println("radixSort1 countingSort countList:" + Arrays.toString(countList));
  27. // 根据计数数组按顺序取出排序内容
  28. for (int i = arr.length - 1; i >= 0; i--) {
  29. int item = arr[i] - min;
  30. int idx = (item / exponent) % range;
  31. // 根据计数位置得到顺序
  32. sortedList[countList[idx] - 1] = arr[i];
  33. countList[idx] -= 1;
  34. }
  35. // 最后赋值给原数据
  36. for (int i = 0; i < arr.length; i++) {
  37. arr[i] = sortedList[i];
  38. }
  39. System.out.println("radixSort1 -> sortedList:" + Arrays.toString(sortedList));
  40. return sortedList;
  41. }
  42. // 基数排序1,按数位大小,基于计数排序实现
  43. public static int[] radixSort1(int arr[]) {
  44. int max = arr[0];
  45. for (int i = 0; i < arr.length; i++) {
  46. if (arr[i] > max) {
  47. max = arr[i];
  48. }
  49. }
  50. // 根据最大值,逐个按进位(基数)来应用排序,exponent即数位。
  51. for (int exponent = 1; (max / exponent) > 0; exponent *= 10) {
  52. countingSort(arr, exponent);
  53. }
  54. return arr;
  55. }
  56. }

 

  

  1. // 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
  2. // 1. 找出数组中最大的数,确定其位数。
  3. // 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
  4. // 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
  5. // 重复步骤2和3,直到按照最高位排序完成。
  6. class RadixSortMSD {
  7. static int[] radixSort(int[] arr) {
  8. int len = arr.length;
  9. // 获取数组最大项
  10. int max = arr[0];
  11. for (int i = 0; i < len; i++) {
  12. if (max < arr[i]) {
  13. max = arr[i];
  14. }
  15. }
  16. // 获取数组最小项
  17. int min = arr[0];
  18. for (int i = 0; i < len; i++) {
  19. if (min > arr[i]) {
  20. min = arr[i];
  21. }
  22. }
  23. // 获取数字一共有几位,减去min得到最大值,以支持负数和减少最大值
  24. int numberOfDigits = (int) (Math.log10(max - min) + 1);
  25. int exponent = (int) (Math.pow(10, numberOfDigits - 1));
  26. // 根据数组最大值,自后向前逐个按数位基数(exponent)比较排序。
  27. return bucketSort(arr, len, exponent);
  28. }
  29. static int[] bucketSort(int[] arr, int len, int exponent) {
  30. System.out.println("origin arr:" + Arrays.toString(arr) + " len=" + len + " exponent:" + exponent);
  31. if (len <= 1 || exponent < 1) {
  32. return arr;
  33. }
  34. // 获取数组最小项
  35. int min = arr[0];
  36. for (int i = 0; i < len; i++) {
  37. if (min > arr[i]) {
  38. min = arr[i];
  39. }
  40. }
  41. // 位数按10递进
  42. int range = 10;
  43. // 定义桶二维数组,长度为10,放入0-9的数字
  44. int[][] buckets = new int[range][len];
  45. // 记录某个桶的最新长度,以便往桶内追加数据。
  46. int[] bucketsCount = new int[range];
  47. for (int i = 0; i < len; i++) {
  48. int item = arr[i] - min;
  49. // 根据数位上的值,把数据追加到对应的桶里,减去min是支持负数
  50. int bucketIdx = (item / exponent) % range;
  51. // 把数据按下标插入到桶里
  52. int numberIndex = bucketsCount[bucketIdx];
  53. buckets[bucketIdx][numberIndex] = arr[i];
  54. bucketsCount[bucketIdx] += 1;
  55. }
  56. // 将每个桶的数据按顺序逐个取出,重新赋值给原数组
  57. int sortedIdx = 0;
  58. for (int i = 0; i < range; i++) {
  59. int[] bucket = buckets[i];
  60. int bucketLen = bucketsCount[i];
  61. // 如果只有一个值,则直接更新到原数组
  62. if (bucketsCount[i] == 1) {
  63. arr[sortedIdx] = bucket[0];
  64. sortedIdx += 1;
  65. } else if (bucket.length > 0 && bucketLen > 0) {
  66. // 如果是数组且记录大于1则继续递归调用,位数降低1位
  67. // 递归调用传参时需要传入当前子序列、子序列长度、当前分解的位数基数
  68. int[] sortedBucket = bucketSort(bucket, bucketLen, (int) (exponent / range));
  69. // 依照已排序的子序列实际长度,把各个桶里的值按顺序赋给原数组
  70. for (int j = 0; j < bucketLen; j++) {
  71. int num = sortedBucket[j];
  72. arr[sortedIdx] = num;
  73. sortedIdx += 1;
  74. }
  75. }
  76. }
  77. System.out.println("exponent:" + exponent + " sorted arr:" + Arrays.toString(arr));
  78. return arr;
  79. }

 

Python

 

  1. """
  2. 基数排序LSD版,本基于桶排序。
  3. 1. 找出数组中最大的数,确定其位数。
  4. 2. LSD是低位到高位,依次按照位数的值将数字放入到不同桶中。
  5. 3. 按照桶顺序重新给数组排序。
  6. 重复步骤2和3,直到排序完成。
  7. """
  8. def radix_sort(arr):
  9. max_value = max(arr) # 找出数组中最大的数
  10. min_value = min(arr) #最小值,为了支持负数
  11. digit = 1 # 从个位开始排序
  12.  
  13. # 每次排序一个数位,从低到高直到排序完成
  14. while (max_value - min_value) // digit > 0:
  15. # 创建10个桶,分别对应0-9的数位值
  16. buckets = [[] for _ in range(10)]
  17. for num in arr:
  18. # 找出当前位数的值
  19. digit_num = (num - min_value) // digit % 10
  20. # 将数字添加到对应数位的桶中,相当于根据数位排序
  21. buckets[digit_num].append(num)
  22. print('buckets:', buckets)
  23. # 通过exend展开数组,相当于逐层添加
  24. arr = []
  25. for bucket in buckets:
  26. arr.extend(bucket)
  27. # 或逐项添加
  28. # for item in bucket:
  29. # arr.append(item)
  30.  
  31. # 数位移动到下一位
  32. digit *= 10
  33.  
  34. return arr
  1. """
  2. 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
  3. 1. 找出数组中最大的数,确定其位数。
  4. 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
  5. 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
  6. 重复步骤2和3,直到按照最高位排序完成。
  7. """
  8. # 桶排序,根据数位递归调用
  9. def bucket_sort(arr, exponent):
  10. print('origin arr:', arr, 'exponent:', exponent)
  11. if (len(arr) <= 1 or exponent <= 0):
  12. return arr
  13. min_value = min(arr)
  14. radix = 10
  15. amount = 10
  16.  
  17. print('prepared arr:', arr, 'exponent:', exponent)
  18. # 构建排序的桶二维列表
  19. buckets = [None] * radix
  20. for i in range(len(arr)):
  21. item = arr[i] - min_value
  22. # 根据数位上的值,把数据追加到对应的桶里,减去min是支持负数
  23. bucketIdx = int(item / exponent) % radix
  24. # 填充空桶,或者提前填充为列表
  25. if buckets[bucketIdx] is None:
  26. buckets[bucketIdx] = []
  27. buckets[bucketIdx].append(arr[i])
  28. print('append to buckets:', buckets)
  29. # 将每个桶的数据按顺序逐个取出,重新赋值给原数组
  30. sortedIdx = 0
  31. for i in range(radix):
  32. bucket = buckets[i]
  33. if bucket is None or len(bucket) < 1:
  34. continue
  35. # 如果是数组则继续递归调用,位数降低1位
  36. sortedBucket = bucket_sort(bucket, exponent // amount)
  37. # 把各个桶里的值按顺序赋给原数组
  38. for num in sortedBucket:
  39. print ('sortedIdx::', sortedIdx)
  40. arr[sortedIdx] = num
  41. print('bucket:', bucket, 'sortedBucket:', sortedBucket,
  42. 'sortedIdx:', sortedIdx, 'set arr:', arr)
  43. sortedIdx += 1
  44.  
  45. print('exponent:', exponent, 'sorted arr:', arr)
  46. return arr
  47. # 基数排序,从高到低逐位排序MSD版,基于桶排序递归实现
  48. def radix_sort_msd(arr):
  49. # 根据最大值,逐个按进位(基数)来应用排序,从高位到低位。
  50. # 获取数字的数位,这减去min_value是为了支持负数
  51. # exponent是最大的数位,由高到低逐位计算
  52. max_value = max(arr)
  53. min_value = min(arr)
  54. numberOfDigits = int(math.log10(max_value - min_value) + 1)
  55. exponent = math.pow(10, numberOfDigits - 1)
  56. return bucket_sort(arr, int(exponent))

 

Go

  1. // 2. 基数排序LSD版,计算最小值,基于计数排序实现
  2. func radixSort2(arr []int) []int {
  3. var arrLen = len(arr)
  4. // 基数exponent按10进位,amount为10
  5. var amount = 10
  6. var sortedList = make([]int, arrLen)
  7. var max = arr[0]
  8. for i := 0; i < arrLen; i++ {
  9. if arr[i] > max {
  10. max = arr[i]
  11. }
  12. }
  13. var min = arr[0]
  14. for i := 0; i < arrLen; i++ {
  15. if arr[i] < min {
  16. min = arr[i]
  17. }
  18. }
  19. // 根据基数求得当前项目对应位置的数值,并给对应计数数组位置加1
  20. // 按最大值补齐数位,基数exponent按10进位
  21. for exponent := 1; ((max - min) / exponent) > 0; exponent *= amount {
  22. // 计数数组,长度为10,0-9一共10个数字
  23. countList := make([]int, amount)
  24. // 根据基数得到当前位数,并给计数数组对应位置加1
  25. for i := 0; i < arrLen; i++ {
  26. var item = arr[i] - min
  27. var idx = (item / exponent) % amount
  28. countList[idx] += 1
  29. }
  30. // 计数排序构建,自前往后,逐个将上一项的值存入当前项
  31. for i := 1; i < amount; i++ {
  32. countList[i] += countList[i-1]
  33. }
  34. fmt.Println("radixSort2 -> countList:", countList)
  35. // 根据计数数组按顺序取出排序内容
  36. for i := arrLen - 1; i >= 0; i-- {
  37. item := arr[i] - min
  38. var idx = (item / exponent) % amount
  39. sortedList[countList[idx]-1] = arr[i]
  40. countList[idx] -= 1
  41. }
  42. // 将新顺序赋值给原数组
  43. for i := 0; i < arrLen; i++ {
  44. arr[i] = sortedList[i]
  45. }
  46. }
  47. return arr
  48. }
  1. // 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
  2. // 1. 找出数组中最大的数,确定其位数。
  3. // 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
  4. // 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
  5. // 重复步骤2和3,直到按照最高位排序完成。
  6. func radixSortMSD(arr []int) []int {
  7. var amount = 10
  8. maxValue := max(arr)
  9. exponent := pow(amount, getNumberOfDigits(maxValue)-1)
  10. bucketSort(arr, exponent)
  11. return arr
  12. }
  13. func bucketSort(arr []int, exponent int) []int {
  14. fmt.Println("origin arr:", arr, "exponent: ", exponent)
  15. if exponent < 1 || len(arr) <= 1 {
  16. return arr
  17. }
  18. var amount = 10
  19. fmt.Println("prepared arr:", arr, "exponent: ", exponent)
  20. buckets := [][]int{}
  21. // 按数位来获取最小值
  22. minValue := getMinValue(arr, exponent)
  23. // 增加偏移以便支持负数
  24. offset := 0
  25. if minValue < 0 {
  26. offset = 0 - minValue
  27. }
  28. // 填充桶二维数组
  29. for i := 0; i < (amount + offset); i++ {
  30. buckets = append(buckets, []int{})
  31. }
  32. // 获取数组项指定数位的值,放入到对应桶中,桶的下标即顺序
  33. for i, num := range arr {
  34. bucketIdx := getDigit(arr, i, exponent) + offset
  35. buckets[bucketIdx] = append(buckets[bucketIdx], num)
  36. }
  37. fmt.Println("append to buckets: ", buckets)
  38. sortedIdx := 0
  39. for _, bucket := range buckets {
  40. if len(bucket) <= 0 {
  41. continue
  42. }
  43. // 递归遍历所有的桶,由里而外逐个桶进行排序
  44. sortedBucket := bucketSort(bucket, exponent/amount)
  45. // 把各个桶里的值按顺序赋给原数组
  46. for _, num := range sortedBucket {
  47. arr[sortedIdx] = num
  48. fmt.Println("bucket:", bucket, "sortedBucket: ", sortedBucket, "sortedIdx:", sortedIdx, "set arr: ", arr)
  49. sortedIdx += 1
  50. }
  51. }
  52. fmt.Println("exponent: ", exponent, "sorted arr: ", arr)
  53. return arr
  54. }
  55. // 获取数字位数
  56. func getNumberOfDigits(num int) int {
  57. numberOfDigits := 0
  58. for num > 0 {
  59. numberOfDigits += 1
  60. num /= 10
  61. }
  62. return numberOfDigits
  63. }
  64. // 获取绝对值
  65. func abs(value int) int {
  66. if value < 0 {
  67. return -value
  68. }
  69. return value
  70. }
  71. // 获取数组最大值
  72. func max(arr []int) int {
  73. maxValue := arr[0]
  74. for i := 1; i < len(arr); i++ {
  75. if arr[i] > maxValue {
  76. maxValue = arr[i]
  77. }
  78. }
  79. return maxValue
  80. }
  81. // 计算数字次幂
  82. func pow(a int, power int) int {
  83. result := 1
  84. for i := 0; i < power; i++ {
  85. result *= a
  86. }
  87. return result
  88. }
  89. // 获取数组项指定数位的最小值
  90. func getMinValue(arr []int, exponent int) int {
  91. minValue := getDigit(arr, 0, exponent)
  92. for i := 1; i < len(arr); i++ {
  93. element := getDigit(arr, i, exponent)
  94. if minValue > element {
  95. minValue = element
  96. }
  97. }
  98. return minValue
  99. }
  100. // 获取数字指定数位的值,超出数位补0,负数返回负数
  101. // 如: 1024, 百位: 100 => 返回 0
  102. // 如: -2048, 千位: 1000 => 返回 -2
  103. func getDigit(arr []int, idx int, exponent int) int {
  104. element := arr[idx]
  105. digit := abs(element) / exponent % 10
  106. if element < 0 {
  107. return -digit
  108. }
  109. return digit
  110. }

 

JS

  1. // 基数排序2,从低到高逐个数位对比排序,基于桶排序,利用JS数组展开来还原数组
  2. function radixSort2(arr) {
  3. // 倒数获取数字指定位置的数
  4. function getDigit(num, position) {
  5. const digit = Math.floor(num / Math.pow(10, position - 1)) % 10
  6. return digit
  7. }
  8. // 获取数组最大数字的位数
  9. function getNumberLength(num) {
  10. let maxLength = 0
  11. while (num > 0) {
  12. maxLength++
  13. num /= 10
  14. }
  15. return maxLength
  16. }
  17. const max = Math.max.apply(null, arr)
  18. const min = Math.min.apply(null, arr)
  19. const maxLength = getNumberLength(max - min)
  20. for (let i = 0; i < maxLength; i++) {
  21. // 每个数位准备10个空数组,用于放数字0-9
  22. const buckets = Array.from({
  23. length: 10
  24. }, () => [])
  25. // 遍历数组将数位上的数放入对应桶里
  26. for (let j = 0, l = arr.length; j < l; j++) {
  27. const item = (arr[j] - min)
  28. // 从后往前获取第x位置的数,通过计算的方式
  29. const num = getDigit(item, i + 1)
  30. // 当前位数如果不为空则添加到基数桶中
  31. if (num !== isNaN) {
  32. buckets[num].push((arr[j]))
  33. }
  34. }
  35. // 将桶逐级展开取出数字,如果支持flat则直接使用数组的flat()
  36. if (buckets.flat) {
  37. arr = buckets.flat()
  38. } else {
  39. // 定定义数组展开函数
  40. // arr = flat(buckets)
  41. }
  42. }
  43. return arr
  44. }
  1. // 基数排序,从高到低逐位排序,递归方式,基于桶排序。具体步骤如下:
  2. // 1. 找出数组中最大的数,确定其位数。
  3. // 2. MSD是从高位开始,依次按照位数的值将数字放入到不同桶中。
  4. // 3. 如果桶里的长度超过1,则通过递归继续按桶排序。当桶里的数据只有1位时添加到原列表对应位置。
  5. // 重复步骤2和3,直到按照最高位排序完成。
  6. function radixSortMSD(arr) {
  7. function bucketSort(arr, exponent) {
  8. console.log('origin arr:', arr, 'exponent:', exponent)
  9. if (!arr || arr.length <= 1 || exponent < 1) {
  10. return arr
  11. }
  12. const min = Math.min.apply(null, arr)
  13. const range = 10
  14.  
  15. // 定义桶二维数组,长度为10,放入0-9的数字
  16. const buckets = []
  17. for (let i = 0; i < range; i++) {
  18. buckets[i] = []
  19. }
  20. for (let i = 0, l = arr.length; i < l; i++) {
  21. const item = arr[i] - min
  22. // 根据数位上的值,把数据追加到对应的桶里,减去min是支持负数
  23. const bucketIdx = Math.floor(item / exponent % range)
  24. // 提前填充空桶或使用时再填充
  25. if (!buckets[bucketIdx]) {
  26. buckets[bucketIdx] = []
  27. }
  28. buckets[bucketIdx].push(arr[i])
  29. }
  30. // 将每个桶的数据按顺序逐个取出,重新赋值给原数组
  31. let sortedIdx = 0
  32.  
  33. for (let i = 0; i < range; i++) {
  34. const bucket = buckets[i]
  35. if (bucket && bucket.length > 0) {
  36. // 如果是数组则继续递归调用,位数降低1位
  37. const sortedBucket = bucketSort(bucket, Math.floor(exponent / range))
  38. // 把各个桶里的值按顺序赋给原数组
  39. sortedBucket.forEach(num => {
  40. arr[sortedIdx] = num
  41. sortedIdx += 1
  42. })
  43. }
  44. }
  45. return arr
  46. }
  47. const max = Math.max.apply(null, arr)
  48. const min = Math.min.apply(null, arr)
  49. // 获取数字一共有几位,减去min得到最大值,以支持负数和减少最大值
  50. const numberOfDigits = Math.floor(Math.log10(max - min) + 1)
  51. const exponent = Math.pow(10, numberOfDigits - 1)
  52. // 根据数组最大值,自后向前逐个按数位基数(exponent)比较排序。
  53. return bucketSort(arr, exponent)
  54. }

 

TS

 

  1. class RadixSort {
  2. // 基数排序,基于计数排序的基础上,按数字的每个位置来排序
  3. countingSort(arr: Array<number>, exponent: number) {
  4. const countList = Array<number>()
  5. const range = 10
  6. countList.length = range
  7. countList.fill(0)
  8. const min = Math.min.apply(null, arr)
  9. for (let i = 0, l = arr.length; i < l; i++) {
  10. const item = arr[i] - min
  11. // 取得数字的最后一位,并给对应计数数组加1
  12. const idx = Math.floor((item / exponent) % range)
  13. countList[idx] += 1
  14. }
  15. console.log('countingSort countList:', countList)
  16. // 根据位置计数,后面的位数为前面的累加之和
  17. for (let i = 1; i < range; i++) {
  18. countList[i] += countList[i - 1]
  19. }
  20. const sortedList = Array<number>()
  21. // 根据计数数组按顺序取出排序内容
  22. for (let i = arr.length - 1; i >= 0; i--) {
  23. const item = arr[i] - min
  24. const idx = Math.floor((item / exponent) % range)
  25. sortedList[countList[idx] - 1] = arr[i]
  26. countList[idx] -= 1
  27. }
  28. // 最后赋值给原数据
  29. for (let i = 0; i < arr.length; i++) {
  30. arr[i] = sortedList[i]
  31. }
  32. return sortedList
  33. }
  34. // 基数排序LSD版,基于计数排序的基础,支持负数,按数字的每个位置来排序
  35. radixSort(arr: Array<number>) {
  36. let sortedList = Array<number>()
  37. const max = Math.max.apply(null, arr)
  38. const min = Math.min.apply(null, arr)
  39. for (
  40. let exponent = 1;
  41. Math.floor((max - min) / exponent) > 0;
  42. exponent *= 10
  43. ) {
  44. sortedList = this.countingSort(arr, exponent)
  45. }
  46. return sortedList
  47. }
  48. }

 

C

  1. // 计数排序,根据基数按位进行计数
  2. void counting_sort(int arr[], int len, int exponent)
  3. {
  4. int sorted_list[len];
  5. int range = 10;
  6. int count_list[range];
  7. // 找出最小值
  8. int min_value = arr[0];
  9. for (int i = 1; i < len; i++)
  10. {
  11. if (arr[i] < min_value)
  12. min_value = arr[i];
  13. }
  14. memset(count_list, 0, range * sizeof(int));
  15. // 根据数字所在位置进行计数
  16. for (int i = 0; i < len; i++)
  17. {
  18. int item = arr[i] - min_value;
  19. int idx = (item / exponent) % range;
  20. count_list[idx]++;
  21. }
  22. // 构建计数排序,当前位置加上左侧位置,后面的位数为前面的累加之和
  23. for (int i = 1; i < range; i++)
  24. {
  25. count_list[i] += count_list[i - 1];
  26. }
  27. // 构建输出数组,根据计数数组按顺序取得排序内容
  28. for (int i = len - 1; i >= 0; i--)
  29. {
  30. int item = arr[i] - min_value;
  31. int idx = (item / exponent) % range;
  32. // 根据位置重排结果,减去min值还原数据
  33. sorted_list[count_list[idx] - 1] = arr[i];
  34. count_list[idx]--;
  35. }
  36. // 复制到数组重排原始数组
  37. for (int i = 0; i < len; i++)
  38. {
  39. arr[i] = sorted_list[i];
  40. }
  41. }
  42. // 基数排序,从低位到高位LSD版,基于计数排序
  43. int *radix_sort(int arr[], int len)
  44. {
  45. int max_value = arr[0];
  46. for (int i = 1; i < len; i++)
  47. {
  48. if (arr[i] > max_value)
  49. max_value = arr[i];
  50. }
  51. int min_value = arr[0];
  52. for (int i = 1; i < len; i++)
  53. {
  54. if (arr[i] < min_value)
  55. min_value = arr[i];
  56. }
  57. // 根据最大值,逐个按进位(基数)来应用排序,exponent即数位基数,按个十百千递增。
  58. for (int exponent = 1; (max_value - min_value) / exponent > 0; exponent *= 10)
  59. {
  60. counting_sort(arr, len, exponent);
  61. }
  62. return arr;
  63. }
  1. // 根据最大长度来获取数字第n位的值,从前往后开始,前面不足最大长度时补零
  2. int get_digit_by_position(int num, int position, int max_length)
  3. {
  4. if (num == 0)
  5. {
  6. return 0;
  7. }
  8. int number_length = (int)log10(num) + 1;
  9. // 查询的位置加上自身长度不足最大长度则返回0
  10. if ((position + number_length) < max_length)
  11. {
  12. return 0;
  13. }
  14. int exponent = (int)pow(10, number_length - position);
  15. int digit = 0;
  16. if (exponent > 0)
  17. {
  18. digit = (num / exponent) % 10;
  19. }
  20. return digit;
  21. }
  22. // 基数排序,从高位到逐个对比排序,通过桶排序递归调用
  23. // arr是数组,len是当前数组长度,position为自前往后的位置,max_length是最大值的数位
  24. int *bucket_sort(int arr[], int len, int position, int max_length)
  25. {
  26. printf("\r\nlen=%d position=%d max_length=%d ", len, position, max_length);
  27. if (len <= 1 || position > max_length)
  28. {
  29. return arr;
  30. }
  31. // 找出最小值
  32. int min_value = arr[0];
  33. for (int i = 1; i < len; i++)
  34. {
  35. if (arr[i] < min_value)
  36. min_value = arr[i];
  37. }
  38. int range = 10;
  39. // 桶一共从0-9十个数字
  40. int buckets[range][len];
  41. for (int i = 0; i < range; i++)
  42. {
  43. // 此处未提前使用,也可以不设置默认值
  44. memset(buckets[i], 0, len * sizeof(int));
  45. // print_array(buckets[i], len);
  46. }
  47. // 默认填充内容为0
  48. int bucket_count_list[range];
  49. memset(bucket_count_list, 0, range * sizeof(int));
  50. for (int i = 0; i < len; i++)
  51. {
  52. int item = arr[i] - min_value;
  53. // 根据数位上的值,减去最小值,分配到对应的桶里
  54. int bucket_idx = get_digit_by_position(item, position, max_length);
  55. // 把数据按下标插入到桶里
  56. int number_idx = bucket_count_list[bucket_idx];
  57. buckets[bucket_idx][number_idx] = arr[i];
  58. bucket_count_list[bucket_idx] += 1;
  59. }
  60. // 将每个桶的数据按顺序逐个取出,重新赋值给原数组
  61. int sorted_idx = 0;
  62. for (int i = 0; i < range; i++)
  63. {
  64. int *bucket = buckets[i];
  65. int bucket_len = bucket_count_list[i];
  66. int bucket_size = sizeof(*bucket) / sizeof(bucket[0]);
  67. // 如果只有一个值,则直接更新到原数组
  68. if (bucket_count_list[i] == 1)
  69. {
  70. arr[sorted_idx] = bucket[0];
  71. sorted_idx += 1;
  72. }
  73. else if (bucket_size > 0 && bucket_len > 0)
  74. {
  75. // 如果是数组且记录追加大于1则继续递归调用,位置增加1位
  76. // 递归调用传参时需要传入当前子序列、子序列长度、当前分解的位数基数
  77. int *sorted_bucket = bucket_sort(bucket, bucket_len, position + 1, max_length);
  78. // 依照已排序的子序列实际长度,把各个桶里的值按顺序赋给原数组
  79. for (int j = 0; j < bucket_len; j++)
  80. {
  81. int num = sorted_bucket[j];
  82. arr[sorted_idx] = num;
  83. sorted_idx += 1;
  84. }
  85. }
  86. }
  87. printf("\r\n position:%d", position);
  88. print_array(arr, len);
  89. return arr;
  90. }
  91. // 计数排序,根据数字的位置逐个对比排序,从高到低MSD,递归方式
  92. int *radix_sort_msd(int arr[], int len)
  93. {
  94. // 找出最大值
  95. int max_value = arr[0];
  96. for (int i = 1; i < len; i++)
  97. {
  98. if (arr[i] > max_value)
  99. max_value = arr[i];
  100. }
  101. // 获取最小项
  102. int min_value = arr[0];
  103. for (int i = 0; i < len; i++)
  104. {
  105. if (min_value > arr[i])
  106. {
  107. min_value = arr[i];
  108. }
  109. }
  110. // 获取数字一共有几位,减去min得到最大值,以支持负数和减少最大值
  111. int max_length = (int)(log10(max_value - min_value) + 1);
  112. // 根据数组最大值的长度,从前往后逐个对比排序。
  113. return bucket_sort(arr, len, 1, max_length);
  114. }

 

C++

  1. // 基数排序,从个位到高位LSD版,基于计数排序实现
  2. int *radixSort(int *arr, int len)
  3. {
  4. // 以10倍递进
  5. int range = 10;
  6. int sortedList[len];
  7. int max = arr[0];
  8. for (int i = 1; i < len; i++)
  9. {
  10. if (arr[i] > max)
  11. {
  12. max = arr[i];
  13. }
  14. }
  15. int min = arr[0];
  16. for (int i = 1; i < len; i++)
  17. {
  18. if (arr[i] < min)
  19. {
  20. min = arr[i];
  21. }
  22. }
  23. // 根据最大值,逐个按进位(基数)来应用排序,exponent即基数。
  24. for (int exponent = 1; ((max - min) / exponent) > 0; exponent *= range)
  25. {
  26. // 计数数组,长度为10,0-9一共10个数字
  27. int countList[range];
  28. memset(countList, 0, range * sizeof(int));
  29. // 根据基数得到当前位数,并给计数数组对应位置加1
  30. for (int i = 0; i < len; i++)
  31. {
  32. int item = arr[i] - min;
  33. int idx = (item / exponent) % range;
  34. countList[idx] += 1;
  35. }
  36. // 计数排序构建,自前往后,逐个将上一项的值存入当前项
  37. for (int i = 1; i < range; i++)
  38. {
  39. countList[i] += countList[i - 1];
  40. }
  41. // 根据计数数组按顺序取出排序内容
  42. for (int i = len - 1; i >= 0; i--)
  43. {
  44. int item = arr[i] - min;
  45. int idx = (item / exponent) % range;
  46. sortedList[countList[idx] - 1] = arr[i];
  47. countList[idx] -= 1;
  48. }
  49. // 复制输出数组到原始数组
  50. for (int i = 0; i < len; i++)
  51. {
  52. arr[i] = sortedList[i];
  53. }
  54. }
  55. return arr;
  56. }

 

链接

基数排序与计数排序、桶排序区别

  1. 基数排序与计数排序、桶排序三者概念很像,但也有不同,其主要差异如下:
  2. 计数排序:根据数组值设定若干个桶,每个桶对应一个数值,将这些桶的值分别存入下一个桶中用于排序,最后按顺序取出对应桶里的值。
  3. 桶排序:根据情况分为若干个桶,每个桶存储一定范围的数值,每个桶再单独排序,最后按桶的顺序取出全部数据。
  4. 基数排序:根据数据的位数来分配桶,每一位对应一个桶,先将全部数据的位数按最大位数对齐,再根据位数上的值大小排列。基数排序基于计数排序或者桶排序。

基数排序算法源码:https://github.com/microwind/algorithms/tree/master/sorts/radixsort

其他排序算法源码:https://github.com/microwind/algorithms

原文链接:https://www.cnblogs.com/letjs/p/17181490.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号