3

手写基数排序算法

 3 years ago
source link: https://xie.infoq.cn/article/19bd9ceb175cd5125e1bee038
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

手写基数排序算法

发布于: 2021 年 07 月 28 日

基数排序（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;}

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK