计数排序，基数排序，桶排序算法

news/2025/2/22 19:41:31

计数排序，基数排序，桶排序算法

计数排序算法：

-------------------------------------------------------------
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();
}


http://www.niftyadmin.cn/n/3354287.html

相关文章

CSS颜色表示法和颜色表

CSS颜色表示法和颜色表

颜色表示法 color name&#xff1a;颜色的名称&#xff1b; color&#xff1a;red&#xff1b; 直接用英文意思来写&#xff0c;但是数量有限&#xff0c;不支持透明颜色 十六进制方式&#xff1a; color&#xff1a;#191d11&#xff1b;所有#开头的都是16进制 rgb&#xff0…
阅读更多...
水泥混凝土摊铺机对于建设中模具的调整和效率的均衡

水泥混凝土摊铺机对于建设中模具的调整和效率的均衡

把对于拦水带等路面外侧设置的构筑建设提速&#xff0c;归根结底要将施工作业的性能提升起来&#xff0c;相比于建设路面而言&#xff0c;旁边的建设难度和耗费的精力可一点都不少&#xff0c;能够适用在项目中的良好性能的机械设备很难得。 模具的重要功能在于针对既有的施工步…
阅读更多...
设计模式之观察者

设计模式之观察者

观察者模式 Observer定义 观察者模式定义了对象之间的一对多依赖&#xff0c;这样一来&#xff0c;当一个对象改变状态时&#xff0c;他的所有依赖者都会收到通知&#xff0c;并自动更新。　　 说明&#xff1a; &#xff08;1&#xff09;对象的一对多的关系中&#xff0c;&qu…
阅读更多...
WebService和Http的POST和GET请求区别和示例

WebService和Http的POST和GET请求区别和示例

web service&#xff08;SOAP&#xff09;Webservice的一个最基本的目的就是提供在各个不同平台的不同应用系统的协同工作能力。Web service 就是一个应用程序&#xff0c;它向外界暴露出一个能够通过Web进行调用的API。SOAP是一种简单基于xml的轻量协议&#xff0c;用户web上交…
阅读更多...
路边石混凝土成型机作业方案与施工注意事项

路边石混凝土成型机作业方案与施工注意事项

作为施工项目中的技术实现手段&#xff0c;路边石混凝土成型机在确认需求参数与尺寸后&#xff0c;配合相应模具来根据厚度宽度等定位参数来准确建设作业&#xff0c;以效率和质量为前提作为基准进行快速准确作业&#xff0c;加载在项目中提现是效率高效的保障。 其中对于各施工…
阅读更多...
uC/OS学习笔记1

uC/OS学习笔记1

这几天稍微空闲点&#xff0c;看了一下uC/OS&#xff0c;用的教材是人民邮电的《uC/OS-II内核分析、移植与驱动程序开发》&#xff0c;刚开始感觉他写的有点稀里糊涂的&#xff0c;自己理一下头绪。uC/OS看到现在&#xff0c;让我感叹这个系统真的是用空间换取时间的典范&#…
阅读更多...
Cache的使用

Cache的使用

1.Cache与Session的区别每个用户都有自己单独的Session对象但是放在Cache中的数据是大家共享的 protected void SetCache() { //判断缓存是否为空 if (Cache["UserInfo"] null) { Bll.UserInfoBll userInfobll new Bll.UserInfoBll(); //如果为空了&#xff0c;需要…
阅读更多...
uC/OS学习笔记2

uC/OS学习笔记2

引 言&#xff1a;1 uC/OS-II的运行机制　　在嵌入式系统的应用中&#xff0c;实时性是一个重要的指标&#xff0c;而优先级翻转是影响系统实时性的重要问题。本文着重分析优先级翻转问题的产生和影响&#xff0c;以及在uC/OS-II中的解决方案。　　uC/OS-II采用基于固定优先级的…
阅读更多...
最新文章

Copyright @ 2022~2023