手写基数排序算法

举报
实力程序员 发表于 2021/07/28 12:45:00 2021/07/28
【摘要】 基数排序(Radix sort)是一种非比较型整数排序算法,其基本思想为:一个待排序整数序列,将其中每个整数看成由不同位构成(比如,个位十位百位千位...)。可以先按个位的数值,将这些数分配到0~9的10个桶中,然后再按从0到9的顺序把这些数从10个桶中收集回来,这时这些数就已经按照个位排好序了。然后再按照10位上的数值,把这些数分配到10个桶中,分配完毕后再次收集回来,这时这些数就已经按照...

基数排序(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的分位值:

2021-07-28_01.jpg


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

2021-07-28_02.jpg


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


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

2021-07-28_03.jpg


从桶中将数据收集回来:
8,36, 341, 45, 257


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

2021-07-28_04.jpg


从桶中将数据收集回来:
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;
}



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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200