手写基数排序算法

基数排序（Radix sort）是一种非比较型整数排序算法，其基本思想为：

一个待排序整数序列，将其中每个整数看成由不同位构成(比如，个位十位百位千位...)。
可以先按个位的数值，将这些数分配到0~9的10个桶中，然后再按从0到9的顺序把这些数从10个桶中收集回来，这时这些数就已经按照个位排好序了。
然后再按照10位上的数值，把这些数分配到10个桶中，分配完毕后再次收集回来，这时这些数就已经按照十位和个位排好序了。
再按百位、千位依次进行上述过程，直到排序的位数到达数列中最大数的最高位，则排序结束。

由于计算机中字符、浮点等都是由整数来表示的，因此基数排序算法是一种普适性的算法，可以用于整数、字符、浮点数排序。

基数排序算法的核心过程，包括：
1. 计算出待排序数列的最大值 max
2. 计算出最大值的最高位位数 div_cnt
3. 分配内存，代表0~9的10个桶，用于存储数据
4. 循环div_cnt 次，每次根据一个分位(个位,十位,百位...)，将这些数据分配到桶中，然后再按桶的顺序将数据收集回来。循环结束后，数据就已经是排好序的了。
5. 释放内存。

基数排序，用一个例子来图解说明：
待排序数列：
36, 341, 45, 8, 257
 
准备10个桶，存储从0到9的分位值：

先将每个整数，按个位上的值，分配到对应的桶中：

从桶中将数据收集回来，得到的数列为：
341， 45， 36， 257， 8

再将每个整数，按十分位上的值，分配到对应的桶中：

从桶中将数据收集回来：
8，36， 341， 45， 257

再将每个整数，按百分位上的值，分配到对应的桶中：

从桶中将数据收集回来：
8，36， 45， 257，341

由于百分位是最大数的最高位，因此排序结束。最终的​排序结果是：
8，36， 45， 257，341

基数排序, 用C 语言实现的代码如下：
(ivec_t 是动态变长数组，存储integer 数据。类似c++中的vector，代码实现见后面)

void radix_sort(int* parr, int count) {
    // 1. compute maximum value
    int max = parr[0];
    for (int i = 1; i < count; i++) {
        if (parr[i] > max) {
            max = parr[i];
        }
    }

    // 2. computer div_cnt
    int div_cnt = 0;
    int max_temp = max;
    while (max_temp > 0) {
        max_temp /= 10;
        div_cnt++;
    }

    // 3. alloc memory for sorting
    ivec_t* pvecs = (ivec_t*)malloc(10 * sizeof(ivec_t));
    for (int i = 0; i < 10; i++) {
        ivec_init(pvecs + i, 8);
    }

    // 4. sort
    int divisor = 1;
    for (int k = 0; k < div_cnt; k++) {
        // clear memory
        for (int i = 0; i < 10; i++) {
            ivec_clear(pvecs + i);
        }

        // distribute to ivec
        for (int i = 0; i < count; i++) {
            int idx = (parr[i] / divisor) % 10;
            ivec_append(pvecs + idx, parr[i]);
        }
        divisor *= 10;

        // collect from ivec
        int idx = 0;
        for (int i = 0; i < 10; i++) {
            int* pbuf = ivec_buf(pvecs + i);
            int cnt = ivec_len(pvecs + i);
            for (int n = 0; n < cnt; n++) {
                parr[idx++] = pbuf[n];
            }
        }
    }

    // 5. free memory
    for (int i = 0; i < 10; i++) {
        ivec_destroy(pvecs + i);
    }
    free(pvecs);
}

上述代码中，使用了 ivec_t 这样的数据结构及相关函数，实现对桶的数据管理。ivec_t 的实现代码如下：

typedef struct ivec_t {
    int cap;
    int len;
    int* pbuf;
} ivec_t;

int ivec_init(ivec_t* pvec, int cap);
int ivec_append(ivec_t* pvec, int val);
int ivec_len(ivec_t* pvec);
int* ivec_buf(ivec_t* pvec);
void ivec_clear(ivec_t* pvec);
int ivec_destroy(ivec_t* pvec);

int ivec_init(ivec_t* pvec, int cap) {
    pvec->len = 0;
    pvec->cap = cap;
    pvec->pbuf = (int*)malloc(cap * sizeof(int));
    return 0;
}

int ivec_append(ivec_t* pvec, int val) {
    if (pvec->len >= pvec->cap) {   // need expand
        int new_cap = pvec->cap * 2;
        int* pnew_buf = realloc(pvec->pbuf, new_cap * sizeof(int));
        if (!pnew_buf) {
            return -1;
        }

        pvec->pbuf = pnew_buf;
        pvec->cap = new_cap;
    }

    pvec->pbuf[pvec->len++] = val;
    return 0;
}

int ivec_len(ivec_t* pvec) {
    return pvec->len;
}

int* ivec_buf(ivec_t* pvec) {
    return pvec->pbuf;
}

void ivec_clear(ivec_t* pvec) {
    pvec->len = 0;
}

int ivec_destroy(ivec_t* pvec) {
    free(pvec->pbuf);
    memset(pvec, 0, sizeof(*pvec));
    return 0;
}

​我的微信号是 实力程序员，欢迎大家转发至朋友圈，分享给更多的朋友。