精华内容
下载资源
问答
  • 基数排序C语言实现

    2011-12-03 16:29:32
    基数排序C语言实现
  • 基数排序 C语言实现 基于单链表代码运行原理 代码 #include <stdio.h> #include <stdlib.h> #define MAXSIZE 100//单链表最大长度 typedef struct node{ int key; struct node *next; }List;//单链表 ...

    基数排序 C语言实现 基于单链表

    代码

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 100//单链表最大长度
    typedef struct node{
        int key;
        struct node *next;
    }List;//单链表
    
    List *CreateList(){
        List *p,*s,*l=NULL;
        int n,i;
        printf("请输入待排序表的长度:");
        do{
            scanf("%d",&n);
            if(n<=0||n>MAXSIZE)
                printf("请输入大于0小于等于%d的长度:",MAXSIZE);
        } while (n<=0||n>MAXSIZE);
        printf("请输入%d个整数:",n);
        for(i=0;i<n;i++){
            if(l==NULL){
                p=(List *)malloc(sizeof(List));
                scanf("%d",&p->key);
                p->next=NULL;
                l=p;
            }else{
                s=(List *)malloc(sizeof(List));
                scanf("%d",&s->key);
                s->next=NULL;
                l->next=s;
                l=s;
            }
        }
        return p;
    }//创建不带头单链表
    
    void ShowList(List *r){
        List *p=r;
        while (p!=NULL){
            printf("%d\t",p->key);
            p=p->next;
        }
    }//输出单链表
    
    int GetNumInPos(int num,int pos){
        int temp=1;
        for(int i=1;i<pos;i++)
            temp*=10;
        return (num/temp)%10;
    }//取某个数在pos位上的数
    
    int GetDigitOfNum(int num){
        int n=1,temp=10;
        while(temp<=num){
            n++;
            temp*=10;
        }
        return n;
    }//求某个数有多少位
    
    int GetMaxDigitOfList(List *r){
        int n,max=0;
        List *p=r;
        while(p!=NULL){
            n=GetDigitOfNum(p->key);
            if(n>max)
                max=n;
            p=p->next;
        }
        return max;
    }//求单链表中数的最大位数
    
    void RadixSort(List *r){
        List *l,*p;
        int index[10][MAXSIZE];//二维数组分类,从上到下0~9,对应数字的每行可保存MAXSIZE个数
        int count[10];//用数组记录被分配基数个数
        int n,i,j,pos;
        for(pos=1;pos <= GetMaxDigitOfList(r);pos++){
            for(i=0;i<10;i++)
                count[i]=0;//开始或每当分类排序完初始为0
            p=r;
            while(p!=NULL){
                n=GetNumInPos(p->key,pos);//获取当前key中在pos位的数
                index[n][count[n]]=p->key;//index[基数][空位]=被分配数
                count[n]++;//对应0~9中,被分配进来的个数
                p=p->next;//定位下一个
            }//分配到数组
            l=r;
            for(i=0;i<10;i++){
                for(j=0;j<count[i];j++){
                    l->key=index[i][j];
                    l=l->next;
                }
            }//重新排序链表
            printf("第%d次排序:\n",pos);
            ShowList(r);
            printf("\n");
        }//从个位到十位再到百位等进行低位优先排序
    }//基数排序
    
    int main() {
        List *r;
        r=CreateList();
        printf("已创建单链表:\n");
        ShowList(r);
        printf("\n");
        RadixSort(r);
        printf("最终排序结果:\n");
        ShowList(r);
        return 0;
    }
    

    运行

    在这里插入图片描述

    原理

    用一维数组保存排序数:

    用二维数组保存分配数:

    01234
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9

    例如要排序的数:

    125494256386142

    先按个位上的数分配:

    01234
    0
    1
    212142
    363
    454
    5425
    686
    7
    8
    99

    个位分配完后,按从上到下从左到右排序:

    121426354425869

    再按十位上的数分配:

    01234
    009
    112
    2425
    3142
    4
    554
    663
    7
    886
    9

    十位分配完后,按从上到下从左到右排序:

    912425142546386

    再按百位上的数分配:

    01234
    0009012054063086
    1142
    2
    3
    4425
    5
    6
    7
    8
    9

    百位分配完后就是最终结果,按从上到下从左到右排序:

    912546386142425

    要排序的数中最大的数有多少位就分配排序多少次。

    展开全文
  • 基数排序(C语言)

    千次阅读 热门讨论 2020-07-16 19:01:40
    基数排序 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用...

    基数排序

    基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog (r) m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

    1.排序原理

    已知序列:{52, 20, 4, 10, 17, 39, 8, 300, 60, 81}

    图示
    在这里插入图片描述

    2.源代码:

    #include<stdio.h>
    #include<string.h>
    #define N 10	//数组长度
    #define D 10	//最大位数
    
    int GetDigit(int M, int i) //取整数M的第i位数
    {
    	while(i > 1)
    	{
    		M /= 10;
    		i--;
    	}
    	return M % 10;
    }
    
    void RadixSort(int num[], int len)
    {
    	int i, j, k, l, digit;
    	int allot[10][N];	//《分配数组》
    
    	memset(allot, 0, sizeof(allot));//初始化《分配数组》
    
    	for(i = 1; i <= D; i++)
    	{
    		//分配相应位数的数据,并存入《分配数组》
    		for(j = 0; j < len; j++)	
    		{			
    			digit = GetDigit(num[j], i);
    			k = 0;
    			while(allot[digit][k])
    				k++;
    			allot[digit][k] = num[j];
    		}
    		//将《分配数组》的数据依次收集到原数组中
    		l = 0; 
    		for(j = 0; j < 10; j++)	
    		{	
    			k = 0;
    			while(allot[j][k] > 0)
    			{
    				num[l++] = allot[j][k];
    				k++;
    			}
    		}
    		//每次分配,收集后初始化《分配数组》,用于下一位数的分配和收集
    		memset(allot, 0, sizeof(allot));
    	}
    }
    
    int main()
    {
    	int num[N] = {52, 20, 4, 10, 17, 39, 8, 300, 60, 81};
    
    	RadixSort(num, N);
    
    	for(int i = 0; i < N; i++)
    		printf("%d ", num[i]);
    	printf("\n");
    	return 0;
    }
    
    展开全文
  • C语言实现简单的基数排序

    千次阅读 2020-01-17 16:25:55
    八大排序算法有:冒泡排序、插入排序、选择排序、快速排序、希尔排序、堆排序、归并排序、基数排序。前面七种网上都有很多例子,但是最后一种基数排序却很少看到,所以我总结了一下,并且自己写了一个简单的实现。 ...
    八大排序算法有:冒泡排序、插入排序、选择排序、快速排序、希尔排序、堆排序、归并排序、基数排序。前面七种网上都有很多例子,但是最后一种基数排序却很少看到,所以我总结了一下,并且自己写了一个简单的实现。
    
    基数排序是一种分配排序,其基本思想是:排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性O(n)。基数排序所做的事情,是对N位分别进行排序。从直觉上来看,人们可能会觉得应该首先按最高有效位进行排序,不过这点与我们的直觉相反,基数排序首先对最低有效位数字进行排序。如果我们每次比较r bits,则需要进行b/r趟,每趟进行计数排序需要O(n+2^r),则总的时间复杂度为O(b/r(n+2^r))。
    
    理论上来说,基数排序的速度是以上几种排序方法中最快的,可以达到O(N),而其它的排序算法最快也只有O(N*logN)。但是,基数排序需要占用额外的空间,而且只支持整数进行排序。
    
    基数排序的演示可以看这里:基数排序
    
    实现代码如下:
    
    #include <stdio.h>
    #include <string.h>
     
    /* 获取输入数字的索引值,dec指定数字的位数,3代表百位数,order指定需要获取哪一位的索引,1代表个位,2代表十位,3代表百位 */
    int get_index(int num, int dec, int order)
    {
        int i, j, n;
        int index;
        int div;
     
        /* 根据位数,循环减去不需要的高位数字 */
        for (i=dec; i>order; i--) {
            n = 1;
            for (j=0; j<dec-1; j++)
                n *= 10;
            div = num/n;
            num -= div * n;
            dec--;
        }
     
        /* 获得对应位数的整数 */
        n = 1;
        for (i=0; i<order-1; i++)
            n *= 10;
     
        /* 获取index */
        index = num / n;
     
        return index;
    }
     
    /* 进行基数排序 */
    void radix_sort(int array[], int len, int dec, int order)
    {
        int i, j;
        int index;     /* 排序索引 */
        int tmp[len];  /* 临时数组,用来保存待排序的中间结果 */
        int num[10];   /* 保存索引值的数组 */
        memset(num, 0, 10*sizeof(int));  /* 数组初始清零 */
        memset(tmp, 0, len*sizeof(int)); /* 数组初始清零 */
     
        if (dec < order) /* 最高位排序完成后返回 */
            return;
     
        for (i=0; i<len; i++) {
            index = get_index(array[i], dec, order);  /* 获取索引值 */
            num[index]++;  /* 对应位加一 */
        }
     
        for (i=1; i<10; i++)
            num[i] += num[i-1]; /* 调整索引数组 */
     
        for (i=len-1; i>=0; i--) {
            index = get_index(array[i], dec, order);  /* 从数组尾开始依次获得各个数字的索引 */
            j = --num[index];  /* 根据索引计算该数字在按位排序之后在数组中的位置 */
            tmp[j] = array[i]; /* 数字放入临时数组 */
        }
     
        for (i=0; i<len; i++)
            array[i] = tmp[i];  /* 从临时数组复制到原数组 */
     
        printf("the %d time\n", order);
        for (i=0; i<30; i++)
            printf("%d  ", array[i]);
        printf("\n");
     
        /* 继续按高一位的数字大小进行排序 */
        radix_sort(array, len, dec, order+1);
     
        return;
    }
     
    int main(int argc, char *argv[])
    {
        int i;
        int array[30] = {258, 976, 515, 337, 359, 701, 916, 494, 303, 175,
                            677, 825, 131, 560, 147, 254, 759, 814, 917, 382,
                            452, 114, 873, 585, 881, 127, 819, 658, 461, 435};
     
        int len = 30;  /* 测试数据个数 */
        int dec = 3;   /* 数据位数,3代表3位数 */
        int order = 1; /* 排序的位数,1代表个位、2代表十位、3代表百位 */
     
        printf("before\n");
        for (i=0; i<30; i++)
            printf("%d  ", array[i]);
        printf("\n");
     
        /* 排序函数,从个位开始 */
        radix_sort(array, len, dec, order);
     
        printf("final\n");
        for (i=0; i<30; i++)
            printf("%d  ", array[i]);
        printf("\n");
     
        return 0;
    }
    
    展开全文
  • c语言实现基数排序

    2021-04-07 16:12:02
    基本实现方式 建立一个个数为10的链表头指针数组以及个数为...当输入完一组非负数时,俺位数由低到高循环,将源链表遍历并将其分别放入每个桶中,再将放入桶中的数由0-9串起来,再串回源链表,即可实现基数排序。 ...
  • 基数排序C语言实现

    千次阅读 2014-11-29 21:53:45
    基数排序C语言实现
  • 基数排序和桶排序、计数排序共同是三种最常用的线性排序算法,这里我们就来深入解析Radix Sort基数排序算法思想及C语言实现示例,需要的朋友可以参考下
  • 基数排序C语言代码实现

    千次阅读 2015-06-26 09:11:15
    } //将排序好的数组恢复成静态链表 void Output(slcell *a, int head) { while (head != -1) { printf("%4d", a[head].num); head = a[head].next; } printf("n"); } //输出静态链表中的值 void main() { int ...
  • 此处的基数排序便是一个很好的例子。 基数排序为桶式排序的推广,即按照次位优先的原则对数据进行多趟桶式排序。 以数组{8, 20, 59, 30, 21, 40, 10, 11, 22, 34, 23, 5, 33, 65, 44, 75, 17, 66, 77, 88, 99,...
  • C语言实现基数排序 文章目录C语言实现基数排序基数排序算法1.定义链结构2.定义链队列结构3.初始化带头结点的链队列4.判断带头结点的链队列是否为空5.带头结点的链队列入队操作6.带头结点的链队列出队操作7.取a的个位...
  • 基数排序 思想:分配 + 收集 基数排序也叫桶排序或箱排序:设置若干个箱子,将关键字为 k 的记录放入第 k 个箱子中,然后在按序号将非空的连接 基数排序:数字是有范围的,均由 0-9 这十个数字组成,则只需要设置十...
  • 基数排序(C语言版)

    千次阅读 2014-10-14 16:38:17
    下面是我用C语言实现的基数排序, 是链式基数排序算法,如果有什么错误请大家指出,谢谢。 #include #include #include #include #define RADIXCOUNT 10 //桶的个数,桶号:0 1 2 ..... 9 #define ...
  • 基数排序 C语言实现

    千次阅读 2013-08-04 23:01:17
    /*被排序元素的最大位数,4则意味着只能排序 #define WIDTH 4  #define MAXK 10 //位数划分基于的基数,10表示为10进制划分 void radixSort(int a[], int n)  { int i; void innerCountingSort(int a[],
  • 基数排序(radix sort),同样时一种非比较的内部排序算法,主要基于多关键字排序的思想进行排序,它将单个关键字按照基数分成“多个关键字”进行排序。例如整数789是一个关键字,可以按照十进制位划分多关键字(十...
  • 上一篇介绍了不稳定的快速排序,这回介绍基数排序 基数排序是基于分配策略的排序,不是一种比较排序,不受到 O(n log n) 下限的影响,是一种稳定的排序算法,并且它可以应用于多关键字排序。 次位优先基数排序 先...
  • 基数排序C语言

    2020-12-12 20:11:47
    基数排序 基数排序(Radix sort)是一种非比较型的排序算法,最早用于解决卡片排序的问题。 它的工作原理是将待排序的元素拆分为k个关键字,其中k为最大值的位数,从低位开始进行稳定排序。(注意:数列中的元素都...
  • 基数排序(radixsort)属于“分配式排序”(distributionsort),又称“桶子法”(bucketsort)或binsort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。 2.基数排序...
  • 排序算法c语言描述---基数排序

    万次阅读 多人点赞 2013-08-14 20:25:24
    排序算法系列学习,主要描述冒泡排序,选择排序,直接插入排序,希尔排序,堆排序,归并排序,快速排序排序进行分析。 文章规划: 一。通过自己对排序算法本身的理解,对每个方法写个小测试程序。 具体思路...
  • /*基数对应管道*/ for (int i = 0; i ; ++i) { /* C99后才支持变量表达式作数组长度*/ pipeLength[i] = 0; /*数组长为变量表达式时无法在定义时进行初始化,需一个一个地赋初值*/ } /*分配到对应管道*/ for (int i =...
  • C语言 基数排序

    2021-06-02 19:22:48
    } //基数排序,适用于桶比较多的场合 //首先,先写一个提取某一位的函数 void get_pos_value(int in,int pos,int &result){ int temp=1; for(int i=1;i;i++){ temp=temp*10; } result=(in/temp)%10; } //这里...
  • 排序【8】之基数排序C语言实现

    千次阅读 2018-01-20 15:10:01
    基数排序(Radix Sorting)是一种借助多关键字排序的思想对单逻辑关键字进行关系的方法。基数排序不需要进行记录关键字间的比较。 主要分为两个过程: (1)分配,先从个位开始,根据位值(0-9)分别放到0~9号桶中...
  • 基数排序,又名握草排序
  • 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序...
  • /*基数排序——LSD*/ /*一共10个桶,从个位开始,将元素按照每一位的数字分配到相应桶中,然后再重新收集,每次收集后,元素之间保持了相对位置(个位小的在前,经过重新分配后,依然保持个位小的在前)最后一次收集...
  • 基数排序单链表实现(C语言)

    千次阅读 2015-04-05 09:59:18
    /*基数排序,单链表实现*/ #ifndef RADIX_SORT_H #define RADIX_SORT_H #include #define FLOWOVER -1 #define LIST_EMPTY -2 struct RadixSort; typedef struct RadixSort * List; typedef struct RadixSort * ...
  • 基数排序 --c语言

    2020-02-10 12:23:02
    基数排序   基数排序是一种针对于有多个关键字的数据的排序算法,不需要两两数据进行排序。排序的思想:     1.按照位数将数据插入到相应队列;     2.按照队列的顺序依次将数据弹出。   算法的过程: ...
  • # 基本思想基数排序(radix sort),同样时一种非比较的内部排序算法,主要基于多关键字排序的思想进行排序,它将单个关键字按照基数分成“多个关键字”进行排序。例如整数789是一个关键...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,143
精华内容 2,457
关键字:

基数排序c语言

c语言 订阅