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

算法描述

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

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

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

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

步骤

获取待排序数组中的最大数的位数
构建二维数组，第一个数组当桶，用于放置从0到9的位数的数据，比如12，45，67，我们以个位数进行筛选的适合，2就放在2的位置的桶里，
二维数组的第二个数组用于放置每个桶的具体的数据，
遍历原数组数据，从低位到高位，每次把对应位置的数据放到指定编号的桶里，然后按照桶的顺序取出数据，重复进行…

LSD 基数排序动图演示

image

时间复杂度

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

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

完整示例

基数类

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

Method radixSort(array As PHA.YX.Arithmetic.Array)
{
    if (array = "")||(array.length() < 2){
        return array
    }
    #dim max as %Integer = array.get(0)
    for i = 0 : 1 : array.length - 1 {
        if (array.get(i) > max) {
            s max = array.get(i)
        }
    }
    
    /* 确定最大的数字有几位 */
    #dim maxDigit as %Integer = 0
    while (max '= 0 ){
        s max = max \ 10
        s maxDigit = maxDigit + 1
    }
    
    /* 每一位的倍数差距 */
    #dim mod as %Integer = 10
    
    /* 定义一个除法的基准值 */
    #dim div as %Integer = 1
    
    /* 这里也可以使用二维数组，外集合表示桶，内集合表示每个桶放入的数据 */
    #dim bucketList as %ListOfObjects = ##class(%ListOfObjects).%New()
    for i = 0 : 1 : 10 {
        
        /* 每一位的值都在0-9之间 */
        #dim list as %ListOfDataTypes = ##class(%ListOfDataTypes).%New()
        d bucketList.Insert(list)
    
    }
    
    for i = 0 : 1 : maxDigit -1 {

        for j = 0 : 1 : array.length() - 1 {
            
            /* 第一次循环，取出个位数字进行一个填充 */
            #dim num = (array.get(j) # mod) \ div
            s subList = bucketList.GetAt(num + 1)
            w "num:" _ num _ " subList:" _ subList _ " array.get(j):" _ array.get(j) _ " mod:"_ mod _ " div:" _ div,!
            d subList.Insert(array.get(j))
        } 
        #dim index as %Integer = 0
        
        /* 回填的操作 */
        for j = 1 : 1 : bucketList.Count()  {
            s subList = bucketList.GetAt(j)
            for k = 1 : 1 : subList.Count()  {
                d array.set(index, subList.GetAt(k))
                s index = index + 1 
            }
            d subList.Clear()
        }
        s mod = mod * 10
        s div = div * 10
    }
    q array
}

}

调用

/// w ##class(PHA.YX.Arithmetic).RadixSort()
ClassMethod RadixSort()
{
    #dim array as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
    d array.init(10)
    d array.insert(0,321)
    d array.insert(1,1234)
    d array.insert(2,543)
    d array.insert(3,324)
    d array.insert(4,24)
    d array.insert(5,960)
    d array.insert(6,540)
    d array.insert(7,672)
    d array.insert(8,783)
    d array.insert(9,1000)
    #dim sort as PHA.YX.Arithmetic.RadixSort = ##class(PHA.YX.Arithmetic.RadixSort).%New() 
    s array = sort.radixSort(array)
    
    d array.output()
    
    q ""
}

DHC-APP>w ##class(PHA.YX.Arithmetic).RadixSort()
num:1 subList:6@%Library.ListOfDataTypes array.get(j):321 mod:10 div:1
num:4 subList:9@%Library.ListOfDataTypes array.get(j):1234 mod:10 div:1
num:3 subList:8@%Library.ListOfDataTypes array.get(j):543 mod:10 div:1
num:4 subList:9@%Library.ListOfDataTypes array.get(j):324 mod:10 div:1
num:4 subList:9@%Library.ListOfDataTypes array.get(j):24 mod:10 div:1
num:0 subList:5@%Library.ListOfDataTypes array.get(j):960 mod:10 div:1
num:0 subList:5@%Library.ListOfDataTypes array.get(j):540 mod:10 div:1
num:2 subList:7@%Library.ListOfDataTypes array.get(j):672 mod:10 div:1
num:3 subList:8@%Library.ListOfDataTypes array.get(j):783 mod:10 div:1
num:0 subList:5@%Library.ListOfDataTypes array.get(j):1000 mod:10 div:1
num:6 subList:11@%Library.ListOfDataTypes array.get(j):960 mod:100 div:10
num:4 subList:9@%Library.ListOfDataTypes array.get(j):540 mod:100 div:10
num:0 subList:5@%Library.ListOfDataTypes array.get(j):1000 mod:100 div:10
num:2 subList:7@%Library.ListOfDataTypes array.get(j):321 mod:100 div:10
num:7 subList:12@%Library.ListOfDataTypes array.get(j):672 mod:100 div:10
num:4 subList:9@%Library.ListOfDataTypes array.get(j):543 mod:100 div:10
num:8 subList:13@%Library.ListOfDataTypes array.get(j):783 mod:100 div:10
num:3 subList:8@%Library.ListOfDataTypes array.get(j):1234 mod:100 div:10
num:2 subList:7@%Library.ListOfDataTypes array.get(j):324 mod:100 div:10
num:2 subList:7@%Library.ListOfDataTypes array.get(j):24 mod:100 div:10
num:0 subList:5@%Library.ListOfDataTypes array.get(j):1000 mod:1000 div:100
num:3 subList:8@%Library.ListOfDataTypes array.get(j):321 mod:1000 div:100
num:3 subList:8@%Library.ListOfDataTypes array.get(j):324 mod:1000 div:100
num:0 subList:5@%Library.ListOfDataTypes array.get(j):24 mod:1000 div:100
num:2 subList:7@%Library.ListOfDataTypes array.get(j):1234 mod:1000 div:100
num:5 subList:10@%Library.ListOfDataTypes array.get(j):540 mod:1000 div:100
num:5 subList:10@%Library.ListOfDataTypes array.get(j):543 mod:1000 div:100
num:9 subList:14@%Library.ListOfDataTypes array.get(j):960 mod:1000 div:100
num:6 subList:11@%Library.ListOfDataTypes array.get(j):672 mod:1000 div:100
num:7 subList:12@%Library.ListOfDataTypes array.get(j):783 mod:1000 div:100
num:1 subList:6@%Library.ListOfDataTypes array.get(j):1000 mod:10000 div:1000
num:0 subList:5@%Library.ListOfDataTypes array.get(j):24 mod:10000 div:1000
num:1 subList:6@%Library.ListOfDataTypes array.get(j):1234 mod:10000 div:1000
num:0 subList:5@%Library.ListOfDataTypes array.get(j):321 mod:10000 div:1000
num:0 subList:5@%Library.ListOfDataTypes array.get(j):324 mod:10000 div:1000
num:0 subList:5@%Library.ListOfDataTypes array.get(j):540 mod:10000 div:1000
num:0 subList:5@%Library.ListOfDataTypes array.get(j):543 mod:10000 div:1000
num:0 subList:5@%Library.ListOfDataTypes array.get(j):672 mod:10000 div:1000
num:0 subList:5@%Library.ListOfDataTypes array.get(j):783 mod:10000 div:1000
num:0 subList:5@%Library.ListOfDataTypes array.get(j):960 mod:10000 div:1000
24
321
324
540
543
672
783
960
1000
1234

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

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

算法描述

步骤

LSD 基数排序动图演示

时间复杂度

完整示例

基数类

调用

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

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