vlambda博客
学习文章列表

第二十一章 Caché 算法与数据结构 基数排序

第二十一章 Caché 算法与数据结构 基数排序

算法描述

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

  • 基数排序:根据键值的每位数字来分配桶;

  • 计数排序:每个桶只存储单一键值;

  • 桶排序:每个桶存储一定范围的数值;

步骤

  1. 获取待排序数组中的最大数的位数

  2. 构建二维数组,第一个数组当桶,用于放置从0到9的位数的数据,比如12,45,67,我们以个位数进行筛选的适合,2就放在2的位置的桶里,

  3. 二维数组的第二个数组用于放置每个桶的具体的数据,

  4. 遍历原数组数据,从低位到高位,每次把对应位置的数据放到指定编号的桶里,然后按照桶的顺序取出数据,重复进行…

LSD 基数排序动图演示

时间复杂度

基数排序的时间复杂度为 O(n)。

基数排序使用桶排序对其每一位进行排序,即每一位的排序时间复杂度为 O(n),假设最大的数有 digit 位,则共需要进行 digit * O(n) 次排序。时间复杂度依旧为 O(n)。

完整示例

基数类

 
   
   
 
  1. Class PHA.YX.Arithmetic.RadixSort Extends %RegisteredObject

  2. {


  3. Method radixSort(array As PHA.YX.Arithmetic.Array)

  4. {

  5. if (array = "")||(array.length() < 2){

  6. return array

  7. }

  8. #dim max as %Integer = array.get(0)

  9. for i = 0 : 1 : array.length - 1 {

  10. if (array.get(i) > max) {

  11. s max = array.get(i)

  12. }

  13. }


  14. /* 确定最大的数字有几位 */

  15. #dim maxDigit as %Integer = 0

  16. while (max '= 0 ){

  17. s max = max \ 10

  18. s maxDigit = maxDigit + 1

  19. }


  20. /* 每一位的倍数差距 */

  21. #dim mod as %Integer = 10


  22. /* 定义一个除法的基准值 */

  23. #dim div as %Integer = 1


  24. /* 这里也可以使用二维数组,外集合表示桶,内集合表示每个桶放入的数据 */

  25. #dim bucketList as %ListOfObjects = ##class(%ListOfObjects).%New()

  26. for i = 0 : 1 : 10 {


  27. /* 每一位的值都在0-9之间 */

  28. #dim list as %ListOfDataTypes = ##class(%ListOfDataTypes).%New()

  29. d bucketList.Insert(list)


  30. }


  31. for i = 0 : 1 : maxDigit -1 {


  32. for j = 0 : 1 : array.length() - 1 {


  33. /* 第一次循环,取出个位数字进行一个填充 */

  34. #dim num = (array.get(j) # mod) \ div

  35. s subList = bucketList.GetAt(num + 1)

  36. w "num:" _ num _ " subList:" _ subList _ " array.get(j):" _ array.get(j) _ " mod:"_ mod _ " div:" _ div,!

  37. d subList.Insert(array.get(j))

  38. }

  39. #dim index as %Integer = 0


  40. /* 回填的操作 */

  41. for j = 1 : 1 : bucketList.Count() {

  42. s subList = bucketList.GetAt(j)

  43. for k = 1 : 1 : subList.Count() {

  44. d array.set(index, subList.GetAt(k))

  45. s index = index + 1

  46. }

  47. d subList.Clear()

  48. }

  49. s mod = mod * 10

  50. s div = div * 10

  51. }

  52. q array

  53. }


  54. }

调用

 
   
   
 
  1. /// w ##class(PHA.YX.Arithmetic).RadixSort()

  2. ClassMethod RadixSort()

  3. {

  4. #dim array as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()

  5. d array.init(10)

  6. d array.insert(0,321)

  7. d array.insert(1,1234)

  8. d array.insert(2,543)

  9. d array.insert(3,324)

  10. d array.insert(4,24)

  11. d array.insert(5,960)

  12. d array.insert(6,540)

  13. d array.insert(7,672)

  14. d array.insert(8,783)

  15. d array.insert(9,1000)

  16. #dim sort as PHA.YX.Arithmetic.RadixSort = ##class(PHA.YX.Arithmetic.RadixSort).%New()

  17. s array = sort.radixSort(array)


  18. d array.output()


  19. q ""

  20. }

 
   
   
 
  1. DHC-APP>w ##class(PHA.YX.Arithmetic).RadixSort()

  2. num:1 subList:6@%Library.ListOfDataTypes array.get(j):321 mod:10 div:1

  3. num:4 subList:9@%Library.ListOfDataTypes array.get(j):1234 mod:10 div:1

  4. num:3 subList:8@%Library.ListOfDataTypes array.get(j):543 mod:10 div:1

  5. num:4 subList:9@%Library.ListOfDataTypes array.get(j):324 mod:10 div:1

  6. num:4 subList:9@%Library.ListOfDataTypes array.get(j):24 mod:10 div:1

  7. num:0 subList:5@%Library.ListOfDataTypes array.get(j):960 mod:10 div:1

  8. num:0 subList:5@%Library.ListOfDataTypes array.get(j):540 mod:10 div:1

  9. num:2 subList:7@%Library.ListOfDataTypes array.get(j):672 mod:10 div:1

  10. num:3 subList:8@%Library.ListOfDataTypes array.get(j):783 mod:10 div:1

  11. num:0 subList:5@%Library.ListOfDataTypes array.get(j):1000 mod:10 div:1

  12. num:6 subList:11@%Library.ListOfDataTypes array.get(j):960 mod:100 div:10

  13. num:4 subList:9@%Library.ListOfDataTypes array.get(j):540 mod:100 div:10

  14. num:0 subList:5@%Library.ListOfDataTypes array.get(j):1000 mod:100 div:10

  15. num:2 subList:7@%Library.ListOfDataTypes array.get(j):321 mod:100 div:10

  16. num:7 subList:12@%Library.ListOfDataTypes array.get(j):672 mod:100 div:10

  17. num:4 subList:9@%Library.ListOfDataTypes array.get(j):543 mod:100 div:10

  18. num:8 subList:13@%Library.ListOfDataTypes array.get(j):783 mod:100 div:10

  19. num:3 subList:8@%Library.ListOfDataTypes array.get(j):1234 mod:100 div:10

  20. num:2 subList:7@%Library.ListOfDataTypes array.get(j):324 mod:100 div:10

  21. num:2 subList:7@%Library.ListOfDataTypes array.get(j):24 mod:100 div:10

  22. num:0 subList:5@%Library.ListOfDataTypes array.get(j):1000 mod:1000 div:100

  23. num:3 subList:8@%Library.ListOfDataTypes array.get(j):321 mod:1000 div:100

  24. num:3 subList:8@%Library.ListOfDataTypes array.get(j):324 mod:1000 div:100

  25. num:0 subList:5@%Library.ListOfDataTypes array.get(j):24 mod:1000 div:100

  26. num:2 subList:7@%Library.ListOfDataTypes array.get(j):1234 mod:1000 div:100

  27. num:5 subList:10@%Library.ListOfDataTypes array.get(j):540 mod:1000 div:100

  28. num:5 subList:10@%Library.ListOfDataTypes array.get(j):543 mod:1000 div:100

  29. num:9 subList:14@%Library.ListOfDataTypes array.get(j):960 mod:1000 div:100

  30. num:6 subList:11@%Library.ListOfDataTypes array.get(j):672 mod:1000 div:100

  31. num:7 subList:12@%Library.ListOfDataTypes array.get(j):783 mod:1000 div:100

  32. num:1 subList:6@%Library.ListOfDataTypes array.get(j):1000 mod:10000 div:1000

  33. num:0 subList:5@%Library.ListOfDataTypes array.get(j):24 mod:10000 div:1000

  34. num:1 subList:6@%Library.ListOfDataTypes array.get(j):1234 mod:10000 div:1000

  35. num:0 subList:5@%Library.ListOfDataTypes array.get(j):321 mod:10000 div:1000

  36. num:0 subList:5@%Library.ListOfDataTypes array.get(j):324 mod:10000 div:1000

  37. num:0 subList:5@%Library.ListOfDataTypes array.get(j):540 mod:10000 div:1000

  38. num:0 subList:5@%Library.ListOfDataTypes array.get(j):543 mod:10000 div:1000

  39. num:0 subList:5@%Library.ListOfDataTypes array.get(j):672 mod:10000 div:1000

  40. num:0 subList:5@%Library.ListOfDataTypes array.get(j):783 mod:10000 div:1000

  41. num:0 subList:5@%Library.ListOfDataTypes array.get(j):960 mod:10000 div:1000

  42. 24

  43. 321

  44. 324

  45. 540

  46. 543

  47. 672

  48. 783

  49. 960

  50. 1000

  51. 1234