不基于比较的排序算法-基数排序

Radix Sort

时间复杂度O(n*k)

最好情况O(n*k)

最坏情况O(n*k)

空间复杂度O(n+k)

Out-place

基数排序是一个非比较的整数排序算法，其基本思想是：

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

每位数字的比较方法可以用计数排序/桶排序 或者其他的排序算法

设待排序的数组R[1..n]，数组中最大的数是d位数，基数为r（如基数为10，即10进制，最大有10种可能，即最多需要10个桶来映射数组元素）。

处理一位数，需要将数组元素映射到r个桶中，映射完成后还需要收集，相当于遍历数组一遍，最多元素数为n，则时间复杂度为O(n+r)。所以，总的时间复杂度为O(d*(n+r))。

基数排序过程中，用到一个计数器数组，长度为r，还用到一个rn的二位数组来做为桶，所以空间复杂度为O(rn)。

基数排序基于分别排序，分别收集，所以是稳定的。

基数查询视频演示https://video.zhihu.com/video/1230429195752083456?player=%7B%22autoplay%22%3Afalse%2C%22shouldShowPageFullScreenButton%22%3Atrue%7D

Java：

public class RadixSort {

    public static int maxBit(int[] arr) {
        int maxNum = arr[0];
        for (int num : arr) {
            if (num > maxNum) {
                maxNum = num;
            }
        }
        int bit = 1;
        while (maxNum >= 10) {
            maxNum /= 10;
            bit++;
        }
        return bit;
    }

    public RadixSort(int[] arr) {
        int maxBit = maxBit(arr);
        int[] counter = new int[10];
        int[] tem = new int[arr.length];
        int k;
        int radix = 1;
        for (int i = 0; i < maxBit; i++) {
            for (int j = 0; j < 10; j++) {
                counter[j] = 0;
            }
            for (int value : arr) {
                k = (value / radix) % 10;
                counter[k]++;
            }
            for (int j = 1; j < 10; j++) {
                counter[j] = counter[j - 1] + counter[j];
            }
            for (int j = arr.length - 1; j >= 0; j--) {
                k = (arr[j] / radix) % 10;
                tem[counter[k] - 1] = arr[j];
                counter[k]--;
            }
            System.arraycopy(tem, 0, arr, 0, arr.length);
            radix = radix * 10;
        }

    }
    
}

Python：

def RadixSort(num_list):
    length = len(num_list)
    max_bit = maxBit(num_list)
    counter = [0] * 10
    tem = [0] * length
    radix = 1
    for i in range(max_bit):
        for j in range(10):
            counter[j] = 0
        for j in num_list:
            k = (j // radix) % 10
            counter[k] += 1
        for j in range(1, 10):
            counter[j] = counter[j - 1] + counter[j]
        m = length - 1
        while m >= 0:
            k = (num_list[m] // radix) % 10
            tem[counter[k] - 1] = num_list[m]
            counter[k] -= 1
            m -= 1
        for j in range(length):
            num_list[j] = tem[j]
        radix *= 10


def maxBit(num_list):
    max_num = num_list[0]
    for i in num_list:
        if i > max_num:
            max_num = i
    bit = 1
    while max_num >= 10:
        max_num //= 10
        bit += 1
    return bit


def main():
    num_list = [10, 9, 56, 19, 28, 37, 34]
    num_list2 = [5, 4, 3, 1, 2]

    RadixSort(num_list)
    print(num_list)


if __name__ == "__main__":
    main()