六狼论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

新浪微博账号登陆

只需一步,快速开始

搜索
查看: 42|回复: 0

常用排序算法的实现(C语言版)-基数排序

[复制链接]

升级  8%

18

主题

18

主题

18

主题

秀才

Rank: 2

积分
62
 楼主| 发表于 2013-1-26 12:28:36 | 显示全部楼层 |阅读模式
基数排序:
#include <stdlib.h> #include "algosort.h"/*被排序元素的最大位数,4则意味着只能排序< 10000 的数*/#define WIDTH 4 #define MAXK 10  //位数划分基于的基数,10表示为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);}/**获取一个数第d位数的值,位数索引从0开始*/int getDValue(int value, int d) {for (;d > 0 && value > 0; d--) {value = value / MAXK;}return value % MAXK;}
您需要登录后才可以回帖 登录 | 立即注册 新浪微博账号登陆

本版积分规则

快速回复 返回顶部 返回列表