1D.md

基数排序

　　基数排序的思路不同于前面的几种排序算法，并不依赖与比较操作。这里我们按基数统计数据的分布，然后按分布信息对数据进行重新排列。从低位到高位如此反复，便能得到全局的有序列。

func RadixSort[T constraints.Integer](list []T) {
    byteWidth := uint(unsafe.Sizeof(T(0)))
    bitWidth := byteWidth*8
    base := T(1) << (bitWidth - 1)
    signed := (base>>bitWidth) != 0
    size := len(list)
    temp := make([]T, size)
    
    if signed {
        for i := 0; i < size; i++ { list[i] += base }       //变int为uint
    }

    const bk = 1 << 8
    var memo [bk]int                                        //计数表
    for step := uint(0); step < bitWidth; step += 8 {
        for i := 0; i < bk; i++ {
            memo[i] = 0
        }
        for i := 0; i < size; i++ {
            radix := uint8(list[i] >> step)
            memo[radix]++                                   //按基数分布计数
        }
        off := 0
        for i := 0; i < bk; i++ {
            memo[i], off = off, off+memo[i]                 //将计数转化为偏移
        }
        for i := 0; i < size; i++ {
            radix := uint8(list[i] >> step)
            temp[memo[radix]] = list[i]                     //对号入座
            memo[radix]++
        }
        list, temp = temp, list
    }
    
    if byteWidth % 2 == 0 {
        if signed {
            for i := 0; i < size; i++ { list[i] -= base }   //变uint为int
        }
    } else {
        if signed {
            for i := 0; i < size; i++ { list[i] = temp[i] - base }
        } else {
            copy(list, temp)
}   }   }

特点 & 局限性

　　基数排序需要O(N+2^m)的额外空间，其中m是基数的位宽。而算法的时间复杂度则为O((w/m)N)，其中w为数据的位宽。由于m通常为很小的常数，基数排序空间开销实际上和归并排序是基本相当的。另外，它同样具备稳定性。
　　基数排序有着时间复杂度上的优势，但它要求参与排序的数据可以按基数分割，而先前介绍的排序算法都只要求数据可比较。可以按基数分割在现实中往往难以满足，就连最常见的有符号整数也不行（可以转换成无符号整数来处理），这大大限制了该算法的适用范围。

---

目录　上一节　下一节