基数排序

 

基本要求： 

从键盘上输入n个程度为m的整数，要求输出这些整数的升序排列。

 

具体要求：

使用的数据结构是队列，利用顺序队列来实现
	
有良好的人机交互
	
能够输出每一趟分配和收集的情况

基本概念：

基数排序属于分配式排序、又称桶子法。通过键值的查询，将要排序的元素分配至某些“桶”中，以达到排序的作用。



具体思想：

以整形为例，将整形10进制按每位拆分，然后从低位到高位依次比较

主要分为两个过程：

分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中

收集，再将放置在0~9号桶中的数据按顺序放到数组中

重复分配收集过程，从个位到最高位为重复次数


代码实现：

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define Radix 10          //代表Radix（10）个队列

typedef int QElemType;
typedef struct
{
    QElemType *base;       //初始化的动态分配空间，存储数据
    int front;              //头指针，指向队列头元素，用来移动
    int rear;               //尾指针，指向队列尾元素的下一位置，确定长度
} SqQueue;


//distribute进行第n趟分配
//原始数据保存在Q.base数组中
//ArrType是SqQueue类型的数组，
void distribute(SqQueue &Q,int n,SqQueue ArrType[])
{
    //quot-商
    //rem-存储每个数据的第n位（即第1位、第2位...第n位）的值
    int i,c,temp,quot,rem;
    //for置空Radix（10）个队列
    for(i=0; i<Radix; i++)
        ArrType[i].front=0;
    //for处理每个数据的第n位
    for(i=0; i<Q.rear; i++)
    {
        //将第i个数据暂存到quot
        quot=Q.base[i];
        c=0;
        //while计算第i个数据的第n位的值并保存到rem
        while(c<n)
        {
            c++;
            rem=quot%Radix;
            quot/=Radix;
        }
        //将第n位为rem的数据复制到第rem个队列
        //即根据数据的第n位的数字rem，将数据分配到第rem个队列的尾部
        ArrType[rem].base[ArrType[rem].front++]=Q.base[i];
    }
    printf("第%d趟分配之后的情况是：\n",n);
    for(i=0; i<Radix; i++)
    {
        temp=ArrType[i].front;
        //if如果第i个队列不为空
        if(temp>0)
        {
            printf("队列[%d]队头指针front->",i);
            for(c=0; c<temp-1; c++)
                printf("%d-",ArrType[i].base[c]);
            printf("%d<-队列[%d]队尾指针rear\n",ArrType[i].base[temp-1],i);
        }
    }
}

//collect进行第n趟收集
//ArrType保存了第n-1趟分配的结果
void collect(SqQueue &Q,int n,SqQueue ArrType[])
{
    //collected记录已收集数据的数量
    int i,collected=0;

    //for将数组ArrType中的数据收集到int型数组Q.base中
    for(i=0; i<Radix; i++)
    {
        //if如果第i个队列不空，就收集它的数据
        if(ArrType[i].front!=0)
        {
            //进行收集(简单地复制到Q.base数组就行了）
            memcpy(Q.base+collected,ArrType[i].base,ArrType[i].front*sizeof(int));
            collected+=ArrType[i].front;
        }
    }
    printf("第%d趟收集之后的情况是：\n",n);
    for(i=0; i<=Q.front-1; i++)
    {
        printf("%d ",Q.base[i]);
    }
    printf("\n\n");
}

//计算每个队列的初始长度（为数据量的1/Radix）
void Ord(SqQueue &Q,SqQueue ArrType[],int M)
{
    int i;
    int temp=M;

    for(i=0; i<Radix; i++)
    {
        //为第i个队列分配空间
        ArrType[i].base=(int*)calloc(temp,sizeof(int));
        ArrType[i].rear=temp;
    }
}

//for进行M（M为输入的每个数据的长度）趟分配和收集
void RadixSort(SqQueue Q,int M,SqQueue ArrType[])
{
    for(int i=1; i<=M; i++)
    {
        distribute(Q,i,ArrType);
        collect(Q,i,ArrType);
    }
}


int main()
{
    int i,M;
    SqQueue Q,ArrType[Radix];
    printf("请输入每个数据的长度：");
    scanf("%d",&M);
    printf("请输入共有多少个数据：");
    scanf("%d",&Q.rear);
    Q.base=(int*)calloc(Q.rear,sizeof(int));
    Q.front=0;
    printf("请输入%d个长度为%d的数据：\n",Q.rear,M);
    for(i=0; i<Q.rear; i++)
        scanf("%d",&Q.base[Q.front++]);
    printf("\n");
    Ord(Q,ArrType,M);
    RadixSort(Q,M,ArrType);
    //以下的free释放动态分配的内存
    free(Q.base);
    for(i=0; i<Radix; i++)
        free(ArrType[i].base);
    system("PAUSE");
    return 0;
}

 

数据处理：





尾言：

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数

在某些时候，基数排序法的效率高于其它的稳定性排序法。

1. LIMS的基本概念
 LIMS实验室管理系统是为实验、检测等业务板块提供流程化、模块化、标准化操作管理系统，打造基于行业法规的实验室全流程质量控制管理系统，实现实验室“人、机、料、法、环”关键环节管理。
 2. LIMS的功能简介
 LIMS管理过程实现实验室信息、实验教学课程模块、仪器设备管理、耗材试剂管理、实验室资源信息交互等管理业务能力的提升。实验过程实现从业务申请、样品交接、任务分配、实验过程(包括仪器自动采集数据)、报告生成、数据及报告的审核批准、报告签发打印(包括电子签名)等全过程“无纸化”。所有流程中的各环节为计算机操作和监控，提高了实验精度，能够灵活应对数据导入、数据查询、数据分析、报表展示等，并能针对用户的设备对接等个性化需求进行功能的定制开发，满足使用者需求。
 3. LIMS在实验室管理中的作用
3.1 提高实验室管理分析水平能力和工作效率
对实验室按照标准体系进行管理，以标准化方式规范质量检验和质量管理工作流程，提高实验室综合管理能力和分析水平，建立起快速高效的监督信息化平台，确保质监工作更好地为生产、科研及客户服务。仪器数据的自动采集可以减少手工录入的错误，加快数据传送的速度；统一实验室业务调度，可以优化实验室工作秩序，减少了工作者精力，提高了工作效率。
3.2 提高分析数据安全性和可靠性
LIMS 系统记录了每个分析数据的原始信息，包括数据生成、修改、审核等每一步过程。在对数据产生疑问时，随时调出该数据对应的原始记录。严格的验证系统使得一丁点的数据修改都将记录在案。分布式的数据存放，防止了数据遭受灾难性的破坏，确保实验室数据安全可靠。
3.3 规范实验室工作流程
LIMS 系统为实验室的工作流程建立严格程序，实现工作流程化。流程化管理方法及工作痕迹记忆功能，使实验室管理人员对实验室的每个情况了如指掌，可以轻松浏览实验室每个员工的工作痕迹，及时发现不符合质量管理体系的行为，并加以改进，规范实验室工作流程。
3.4 降低实验室运行成本
通过对数据的统计与趋势分析，可以追踪实验室所有试剂、样品等材料的出入库进行严格管理，建立合理的库存量，加强成本考核，降低实验费用。自动生成各类报表，提高无纸化管理水平。LIMS 系统给实验室各级管理及部门人员创造一个功能强大、方便实用的工作平台，日常事务基于该系统进行处理，减少人员配制，提高工作效率。
3.5 为实验室领导决策提供依据
LIMS 系统强大的统计查询功能使实验室管理更加科学化，定量化。用LIMS前，原材料使用情况，仪器等管理都要有专职管理人员。现在只要根据需要选择不同的查询条件很快就会查出你想要的信息；并通过设定材料使用、设备使用记录、工作任务等各种提醒，LIMS会自动生成提醒，使实验室的负责人做到决策有依据。
4. LIMS的应用
 实验室是获取数据并对数据进行科学分析的场所，实验室工作流程的规范化是实验室信息化管理的基础，实验室要适应新时期工作的需求和市场环境，必须提高实验室管理水平。LIMS可适用于高校科研、医院中心实验室、科研院所、生物制药、制造业环境监测、煤炭矿产、石油化工、生物制药等行业实验室，为检验检测等实验室。有效推动实验室进行信息化建设，实现现代化实验室管理。