计数排序，基数排序，桶排序算法
计数排序算法：
-------------------------------------------------------------
template <class Type>
void CountingSort(int a[],int b[],int k)
{
int i,*c;
c=(int*)malloc(sizeof(int)*k);
for(i=0;i<k;i++)
c[i]=0;
for(i=0;i<MAX;i++)
c[a[i]]=c[a[i]]+1;
for(i=1;i<=k;i++)
c[i]=c[i]+c[i-1];
for(i=MAX-1;i>=0;i--)
{
b[c[a[i]]-1]=a[i];
c[a[i]]=c[a[i]]-1;
}
}
基数排序算法:
----------------------------------------------------------------
void radix_sort(dls *L,int k)
{
dls *Lhead[10],*p;
int i,j,n;
for(i=0;i<NUMLEN;i++){
for(j=0;j<10;j++)
{ Lhead[j]=(dls*)malloc(sizeof(dls));
Lhead[j]->prior=Lhead[j]->next=Lhead[j];
}
printf("/n Sort %d:",i+1);
while(L->next!=L){
p=del_entry(L);
j=get_digital(p,i);
add_entry(Lhead[j],p);
}
for(n=0;n<10;n++)
{
append(L,Lhead[n]);
}
for(n=0;n<ARRAYLEN+1;n++)
{ L=L->next;
if(L->data!=0)
{
printf(" %d",L->data);
}
}
}
}
桶排序算法：
-----------------------------------------------------------------------
void BucketSon(R)
{ //对R[0..n-1]做桶排序，其中0≤R[i].key<1(0≤i<n)
for(i=0，i<n;i++) //分配过程．
将R[i]插入到桶B[「n(R[i].key)」]中； //可插入表头上
for(i=0;i<n;i++) //排序过程
当B[i]非空时用插人排序将B[i]中的记录排序；
for(i=0，i<n；i++) //收集过程
若B[i]非空，则将B[i]中的记录依次输出到R中；
}
附C语言实现程序：
计数排序：
----------------------------------------------------------------------
//输入的数最大值不能大于MAX
#include "stdio.h"
#define MAX 5
void CountingSort(int a[],int b[],int k)
{
int i,*c;
c=(int*)malloc(sizeof(int)*k);
for(i=0;i<k;i++)
c[i]=0;
for(i=0;i<MAX;i++)
c[a[i]]=c[a[i]]+1;
for(i=1;i<=k;i++)
c[i]=c[i]+c[i-1];
for(i=MAX-1;i>=0;i--)
{
b[c[a[i]]-1]=a[i];
c[a[i]]=c[a[i]]-1;
}
}
void main()
{
int a[MAX],b[MAX];
int i,j,k,min;
for(i=0;i<MAX;i++)
{ printf("/n Intput the %d number:",i+1);
scanf("%d",&a[i]);
}
CountingSort(a,b,MAX);
printf("CountingSort result:");
for(i=0;i<MAX;i++)
printf(" %d",b[i]);
}
基数排序：
--------------------------------------------------------------
#include"stdio.h"
#define ARRAYLEN 5
#define NUMLEN 3
typedef struct dnode
{ int data;
struct dnode *prior,*next;
}dls;
add_element(dls *p,int x) /*插入算法 */
{
dls *s;
s=(dls*)malloc(sizeof(dls));
s->data=x;
s->prior=p->prior;
s->next=p;
p->prior->next=s;
p->prior=s;
}
int initlist(dls *L) /*初始化,有头接点*/
{
L->data=0;
L->next =L;
L->prior=L;
}
dls *del_entry(dls *L)
{
dls *p;
p=L->next;
if(p!=L)
{
p->prior->next=p->next;
p->next->prior=p->prior;
}
else p=NULL;
return p;
}
void add_entry(dls *L,dls *p)
{
p->prior=L->prior;
p->next=L;
L->prior->next=p;
L->prior=p;
}
int power(int i,int j)
{
int s=1,n;
for(n=0;n<j;n++)
{
s=s*i;
}
return s;
}
int get_digital(dls *p,int i)
{
int key;
key=p->data;
if(i!=0)
key=key/power(10,i);
return key%10;
}
void append(dls *L,dls *L1)
{
if(L1->next!=L1)
{ L->prior->next=L1->next;
L1->next->prior=L->prior;
L1->prior->next=L;
L->prior=L1->prior;
}
}
void radix_sort(dls *L,int k)
{
dls *Lhead[10],*p;
int i,j,n;
for(i=0;i<NUMLEN;i++){
for(j=0;j<10;j++)
{ Lhead[j]=(dls*)malloc(sizeof(dls));
Lhead[j]->prior=Lhead[j]->next=Lhead[j];
}
printf("/n Sort %d:",i+1);
while(L->next!=L){
p=del_entry(L);
j=get_digital(p,i);
add_entry(Lhead[j],p);
}
for(n=0;n<10;n++)
{
append(L,Lhead[n]);
}
for(n=0;n<ARRAYLEN+1;n++)
{ L=L->next;
if(L->data!=0)
{
printf(" %d",L->data);
}
}
}
}
void main()
{
int i,a[ARRAYLEN];
dls *L,*p;
L=(dls*)malloc(sizeof(dls));
p=(dls*)malloc(sizeof(dls));
initlist(L);
initlist(p);
printf("Warning:The length of the number must less than %d",NUMLEN);
for(i=0;i<ARRAYLEN;i++)
{ printf("/n Please input the %d number:",i+1);
scanf("%d",&a[i]);
}
printf("/n The sort number:");
for(i=0;i<ARRAYLEN;i++)
{ printf(" %d",a[i]);
}
for(i=0;i<ARRAYLEN;i++)
{
add_element(L,a[i]);
}
radix_sort(L,NUMLEN);
getch();
}
桶排序：
-------------------------------------------------------------
/*桶排序(元素取值范围为[0,1]) */
#include<stdio.h>
#include<stdlib.h>
#define ArrayLen 5 /*数组的长度*/
#define BucketNum 10 /*桶的数量*/
typedef struct node {
float value;
struct node *next;
}node;
init_bucket(node **bucket) /* 初始化 BucketNum 个桶*/
{ int i;
for (i = 0;i <BucketNum;i++){
bucket[i] = (node *)malloc(sizeof(node));
bucket[i]->value = 0;
bucket[i]->next = 0;
}
}
insert_node(node **bucket,float a[]) /* 向桶里插入数组a[]里面的数据*/
{
node *n2, *n1;
int i, j;
for (i = 0;i<ArrayLen;i++) {
j = a[i] * BucketNum;
if (bucket[j]->value == 0 && bucket[j]->next == 0)
bucket[j]->value = a[i];
else{
n2 = bucket[j] ;
while (n2 -> next)
n2 = n2 -> next;
n2 -> next = (node *) malloc(sizeof(node));
n2 = n2 -> next;
n2 -> next = 0;
n2 -> value = a[i];
}
}
}
swanp_append(node **bucket,float a[]) /* 对每个桶进行排序，并把所有桶的数据按顺序附加在a[]上*/
{
node *n2, *n1;
float temp;
int i, j=0;
for (i = 0;i < BucketNum;i++){
if (bucket[i]->next == 0 && bucket[i]->value == 0)
continue;
if (bucket[i]->next){
n1 = bucket[i];
while (n1) {
n2 = n1->next;
while (n2) {
if (n1->value > n2->value){
temp = n1 -> value;
n1 -> value = n2 -> value;
n2 -> value = temp;
}
n2 = n2 -> next;
}
n1 = n1 -> next;
}
}
n1 = bucket[i];
while (n1) {
a[j++] = n1 -> value;
n2 = n1;
n1 = n1 -> next;
free(n2);
}
}
}
void bucket_sort(float a[]){
node **bucket, *n2, *n1;
float temp;
int i, j;
bucket = (node **)malloc(sizeof(node *) * BucketNum);
init_bucket(bucket); /* 初始化 BucketNum 个桶*/
insert_node(bucket,a); /* 向桶里插入数组a[]里面的数据*/
swanp_append(bucket,a); /* 对每个桶进行排序，并把所有桶的数据按顺序附加在a[]上*/
free(bucket);
}
void main(){
int i;
float a[ArrayLen];
printf("Warning:the Num must between 0 to 1 !!");
for (i=0;i<ArrayLen;i++){
printf("/n Please input the %d Num: ",i+1);
scanf("%f",&a[i]);
}
bucket_sort(a);
printf("/n The bucket_sort result: ");
for (i=0;i<ArrayLen;i++)
printf(" %.2f ", a[i]);
getch();
}
