浏览 3485 次
锁定老帖子 主题:常用排序算法的实现(C语言版)-基数排序
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2012-08-01
#include <stdlib.h> #include "algosort.h" /*被排序元素的最大位数,4则意味着只能排序< 10000 的数*/ #define WIDTH 4 #define MAXK 10 void radixSort(int a[], int n) { int i; void innerCountingSort(int a[], int n, int d); for (i = 0; i < WIDTH; i++) { innerCountingSort(a, n, i); } } void innerCountingSort(int a[], int n, int d) { int i, j, x, k[MAXK] = {0}; int *ip = (int *)malloc(n * sizeof(int)); int *bp = (int *)malloc(n * sizeof(int)); int getDValue(int value, int d); for (i = 0; i < n; i++) { ip[i] = getDValue(a[i], d); k[ip[i]]++; } for (j = 1; j < MAXK; j++) { k[j] = k[j] + k[j-1]; } for (i = n - 1; i >= 0; i--) { bp[k[ip[i]] - 1] = a[i]; k[ip[i]]--; } for (i = 0; i < n; i++) { a[i] = bp[i]; } free(ip); free(bp); } int getDValue(int value, int d) { for (;d > 0 && value > 0; d--) { value = value / MAXK; } return value % MAXK; } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |