写点什么

手写基数排序算法

发布于: 22 小时前
手写基数排序算法

基数排序(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;}
复制代码


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

发布于: 22 小时前阅读数: 8
用户头像

实力程序员,用实力说话! 2021.05.24 加入

超过20年一线产品研发和技术管理的实力程序员

评论

发布
暂无评论
手写基数排序算法