精华内容
下载资源
问答
  • 在进行高考分数处理时,除了需对总分进行排序外,不同的专业对单科分数的要求也不同,因此尚需在总分相同的情况下,按用户提出的...排序方法有很多种,这里就要设计程序比较一下内部排序和多关键字排序所用时间的长短。
  • 数据结构课程设计 多关键字排序使用自动生成器生成分数对高考成绩进行排序
  • 数据结构——多关键字排序 问题描述:多关键字的排序有其一定的实用范围。例如:在进行高考分数处理时,除了需对总分进行排序外,不同的专业对单科分数的要求不同,因此尚需在总分相同的情况下,按用户提出的单科...
  • 数据结构课程设计多关键字排序 利用多关键字排序进行高考分数处理,除了需对总分进行排序外,不同的专业对单科分数的要求不同,因此在总分相同的情况下,按用户提出的单科分数的次序要求排出考生录取的次序 内包涵...
  • 直接插入排序,希尔排序,简单选择排序,冒泡排序,快速排序,堆排序,归并排序主要通过某种策略移动,选择或交换关键字来实现,关键字选择上,为了简便起见,都是整形数据关键字间的比较,也都是直观的大小比较。...
  • MulitCompare.c #include<stdio.h> typedef struct _tag_DataElem { char desc[20]; int key1; int key2; } DataElem; int compare1(DataElem* ld,DataElem* rd) { int ret = 0;...r...

    MulitCompare.c

    #include<stdio.h>
    
    typedef struct _tag_DataElem
    {
    	char desc[20];
    	int key1;
    	int key2;
    } DataElem;
    
    int compare1(DataElem* ld,DataElem* rd)
    {
    	int ret = 0;
    	
    	if(ld->key1>rd->key1)
    	{
    		ret = 1;
    	}
    	else if(ld->key1==rd->key1)
    	{
    		if(ld->key2>rd->key2)
    		{
    			ret = 1;
    		}
    		
    		if(ld->key2<rd->key2)
    		{
    			ret = -1;
    		}
    	}
    	else
    	{
    		ret = -1;
    	}
    	
    	return ret;
    }
    
    int compare2(DataElem* ld,DataElem* rd)
    {
    	return (ld->key1*100+ld->key2)-(rd->key1*100+rd->key2);
    }
    
    int main()
    {
    	DataElem d1 = {"d1",91,88};
    	DataElem d2 = {"d2",90,95};
    	
    	printf("Compare1 %s and %s:%d\n",d1.desc,d2.desc,compare1(&d1,&d2));
    	printf("Compare2 %s and %s:%d\n",d1.desc,d2.desc,compare2(&d1,&d2));
    	
    	return 0;
    }
    

    运行效果:
    在这里插入图片描述

    展开全文
  • 多关键字排序实验

    2018-07-08 00:40:00
    了解多关键字的使用范围,并实现对牌照按多关键字排序后的快速查找。 【问题描述】 为加快速度需先对数据记录按关键字排序,在汽车数据模型中,汽车是关键字,而且是具有结构特点的一类关键字。因为汽车牌照是汉字...

    一、实习目的

        了解多关键字的使用范围;编写程序实现对汽车牌照的排序。

    二、实验原理

    了解多关键字的使用范围,并实现对牌照按多关键字排序后的快速查找。

    【问题描述】

    为加快速度需先对数据记录按关键字排序,在汽车数据模型中,汽车是关键字,而且是具有结构特点的一类关键字。因为汽车牌照是汉字,字母和数字混编的,例如:AD7328。这种记录集合是一个适于利用多关键字进行排序的典型例子。

    【基本任务】

    (1)利用链式基数排序方法实现排序。

    (2)在排序的基础上,利用二分查找的思想,实现对汽车记录按关键字的查找。

    三、参考程序

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

    struct sort{
    int zi[3];
    };
    sort a[8]={{1,2,3},{1,6,3},{1,0,9},{7,3,1},{2,3,9},{1,4,5},{7,1,8},{2,3,8}};
    void paixu(sort *a,int radix,int size,int k){
    int *temp,i,number=0,number1=0,j,z;
    sort *b;
    z=k;
    temp=(int *)malloc(radix*sizeof(int));
    b=(sort *)malloc(number*sizeof(sort));
    while(k--){
    for(i=0;i<radix;i++){
    temp[i]=0;
    }
    for(i=0;i<size;i++){
    number=a[i].zi[k];
    temp[number]=temp[number]+1;
    }
    printf("\n----\n");
    for(i=0;i<radix-1;i++){
    temp[i+1]=temp[i+1]+temp[i];
    }

    for(i=0;i<size;i++){
    number1=a[i].zi[k];
    temp[number1]=temp[number1]-1;
    b[temp[number1]]=a[i];


    }


    for(i=0;i<size;i++){
    a[i]=b[i];
    }

    printf("\n---------------\n");
    if(k==0)
    break;

    }
    for(i=0;i<size;i++){
    for(j=0;j<z;j++)
    printf("%d",a[i].zi[j]);
    printf("\n");
    }
    free(temp);
    free(b);


    }
    int main(){

    int size=8,k=3,radix=101;

    paixu(a,radix,size,k);
    return 0;
    }

    转载于:https://www.cnblogs.com/huifeidezhuzai/p/9278967.html

    展开全文
  • ????表排序 ????物理排序 ????桶排序 ????基数排序 ????多关键字排序 ????各种排序算法的比较 学习资源来源: 浙大 数据结构

    📖表排序

    在这里插入图片描述

    📖物理排序

    在这里插入图片描述
    在这里插入图片描述

    📖桶排序

    在这里插入图片描述

    📖基数排序

    在这里插入图片描述

    📖多关键字排序

    在这里插入图片描述
    在这里插入图片描述

    📖各种排序算法的比较

    在这里插入图片描述

    学习资源来源:
    浙大 数据结构

    展开全文
  • 多关键字排序的实现

    2013-03-15 11:52:06
    武汉理工大学数据结构课程设计,多关键字排序的实现
  • 基数排序排序 首先来看看桶排序: 为什么桶排序的时间复杂度是O(M+N)? 因为分配的时间复杂度是M(也就是桶的数量),而收集起来的时间复杂度是N,因此最终时间复杂度是O(M+N)。 上面那种是理想的桶排序,因为...

    基数排序

    桶排序

    首先来看看桶排序:
    在这里插入图片描述
    如果学生有1000个,我们只需要设置100个桶即可,然后按照桶从0-100来按顺序排序即可。

    为什么桶排序的时间复杂度是O(M+N)?
    因为分配的时间复杂度是M(也就是桶的数量),而收集起来的时间复杂度是N,因此最终时间复杂度是O(M+N)。

    上面那种是理想的桶排序,因为最终成绩的范围是在小范围内。
    但是如果成绩的范围很大:
    在这里插入图片描述
    对于一个数,例如523,排序的思想很简单,比它大的排它后面,比它小的排它前面。
    那么一个数如果比523小,可以分为三种情况:

    1. 百位数比5小
    2. 百位数=5,十位数比2小
    3. 百位数=5,十位数=2,个位数比3小

    那接下来来介绍一下基数排序,它是在桶排序的基础上进行优化的。基数排序就是对上面这三种情况都进行了排序。

    基数排序又称多关键字排序,分为两种,MSD(Most Significant Digit)和LSD(Least Significant Digit)

    其中我们看MSD,花色是更为重要的,其次看面值,而MSD就是给花色建4个桶,然后在桶内再用别的排序方法。
    在这里插入图片描述
    LSD就相反:
    在这里插入图片描述

    在大多数情况下LSD会比MSD的效率更高。

    算法原理

    那详细讲下多关键字排序的算法(这里采用LSD):

    拿数字做例子(注意结合上面我说的523):
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    链式基数排序

    在基数排序的实现方法中,通常用链式基数排序来实现:

    使用链表效率更高,更方便些。当收集时,只需要修改指针,不需要移动元素

    在这里插入图片描述
    例如对三位数进行排序,我们可以这样:
    在这里插入图片描述
    (这里的队列其实不是stl的队列,而是类似桶的存在)

    队列头尾指针也可以使用二级指针:
    node **f;
    node **r;

    f=new node*[10]; r=new node*[10];

    或者使用队列: queue q[10];

    我们需要进行n趟分配和收集,n为数字的长度,每次分配和收集需要做这些事情:
    在这里插入图片描述
    在这里插入图片描述

    看下面这个例子

    在这里插入图片描述

    而每次分配完之后需要将结果收集起来,从左至右(也就是从小到大、也就是升序)的收集起来。

    然后接下来从最次位一直到第一位,对每种情况都分配桶。
    在这里插入图片描述
    在这里插入图片描述
    最后收集的时候就可以得到排序的结果了,排序的次数是固定的,是你这个数的长度。

    其实不难理解,对于上面的第一种情况,在第三趟分配和收集的时候会解决。
    对于上面的第二种情况(百位相同十位不同),在第二趟分配和收集的时候会解决。
    而上面的第三种情况,在第三趟分配和收集的时候会解决。

    收集的作用

    为什么分配完后要收集?
    收集有什么作用?为什么可以体现这种作用?

    在每次分配完桶的时候,要把结果从前往后串联下来,(可以想象一下按顺序整理扑克牌,A在最左边,K在最右边,然后从左往右把牌都收起来)。

    例如523和521
    收集的目的是为了针对上面所说的第三种情况,因为我们可以知道如果百位和十位相同,那么百位和十位分配桶的时候,是会分配到一个桶里面的。

    那么我们希望最终结果中,百位和十位相同的情况下,个位小的,应该在数组的前面

    因此这时候在最终的分配中,因为百位和十位相同,所以这两个在一个桶里,这时候我们就希望最终个位小的应该在队列更靠近前面的地方,这通过什么来实现呢?在链表结构中是表尾插入,那这就看,谁先插入,谁就在前面。
    那这靠什么来实现呢?就靠最开始个位分配桶的时候,我们是从小的(也就是左边)开始往大的(也就是右边)串联起来,这就保证了,个位小的会出现在前面,也就是我们重新进行分配的时候,个位小的会更先进行分配。

    性能分析

    在这里插入图片描述
    在这里插入图片描述

    代码实现

    要注意几个问题:
    1、给定一组数据,到底要进行多少趟?
    输入数据的同时,选择出最大的数,然后转换成字符串,求其长度
    #include<bits/stdc++.h>
    stringstream sstr;
    sstr << max;
    string s= sstr.str(); //或者string s; sstr>>s;
    weishu=s.length();

    或者写个循环,每次除以10(同时计数),直到商为0

    2、如何求第i位的值?
    for(i=1;i<=weishu;i++)
    for(j=1;j<=len;j++)
    int temp=(data[j] / (int)pow(10,i-1)) % 10;

    class node{
    public:   //结点结构
      int e; 
      node *next;
      node(){next=NULL;}
    };
    
    class Sort{
        int len;    //数据长度
        node *head; //头结点
        node *f[10];//队头指针
        node *r[10];//队尾指针
        int weishu; //处理位数
    public: //各种方法  
    	void init(){//将队头队尾指针设置成NULL
            for(int i=0;i<10;i++){
                f[i]=NULL;
                r[i]=NULL;
            }
        }
    	 void RadixSort(){
    	     int i; node* p;
    	     for(i=1;i<=weishu;i++){
    	        init();   //将队头队尾指针设置成NULL
    	
    	        p=head->next; //开始一趟分配的过程
    	        while(p){
    	           int w=( p->e /(int)pow(10,i-1))%10; //取得第i位的数据
    	           if(f[w]==NULL)   f[w]=p; //若是该队列的第一个数据
    	           else   r[w]->next=p; //否则,在队尾插入
    	           r[w]=p; //队尾指针指向新插入的数据
    	           p=p->next;
    	        }
    	        p=head;   //开始一趟收集的过程
    	        for(int i=0;i<10;i++){  //共10个队列
    	           if(f[i]){ //若第i个队列不空
    	                p->next=f[i];
    	                p=r[i];
    	            }
    	         }
    	
    	         p->next=NULL;  //收集结束,链表加上结束标志。
    	     }
    	}
    }
    

    设立队尾指针的原因

    看图举例
    在这里插入图片描述
    如果不设立队尾指针,那么我们遍历十个队列的每一个队列的时候,比如遍历f[0],从f[0]的第一个元素到最后一个元素,此时遍历:008 063 083 184 589,会把不在f[0]的但是在f[0]最后一个元素后面链接的元素也遍历了!

    因此需要设立队尾指针作为哨兵来查看是否遍历到了最后一个元素。

    例题及完整代码

    在这里插入图片描述
    样例输入
    2
    10 278 109 63 930 589 184 505 269 8 83
    6 57 0 93 19 18 99

    样例输出
    0:->930->^
    1:NULL
    2:NULL
    3:->63->83->^
    4:->184->^
    5:->505->^
    6:NULL
    7:NULL
    8:->278->8->^
    9:->109->589->269->^
    930 63 83 184 505 278 8 109 589 269
    0:->505->8->109->^
    1:NULL
    2:NULL
    3:->930->^
    4:NULL
    5:NULL
    6:->63->269->^
    7:->278->^
    8:->83->184->589->^
    9:NULL
    505 8 109 930 63 269 278 83 184 589
    0:->8->63->83->^
    1:->109->184->^
    2:->269->278->^
    3:NULL
    4:NULL
    5:->505->589->^
    6:NULL
    7:NULL
    8:NULL
    9:->930->^
    8 63 83 109 184 269 278 505 589 930

    0:->0->^
    1:NULL
    2:NULL
    3:->93->^
    4:NULL
    5:NULL
    6:NULL
    7:->57->^
    8:->18->^
    9:->19->99->^
    0 93 57 18 19 99
    0:->0->^
    1:->18->19->^
    2:NULL
    3:NULL
    4:NULL
    5:->57->^
    6:NULL
    7:NULL
    8:NULL
    9:->93->99->^
    0 18 19 57 93 99

    答案代码:

    #include<iostream>
    #include<cmath>
    using namespace std;
    class node{
    public:   //结点结构
        int e;
        node *next;
        node(){next=NULL;}
    };
    
    class Sort{
        int len;    //数据长度
        node *head; //头结点
        node *f[10];//队头指针
        node *r[10];//队尾指针
        int weishu; //处理位数
    public: //各种方法
        Sort(){
            weishu=0;
            cin>>len;
            head=new node;
            int max=0;
            for(int i=0;i<len;i++){
                int num;
                cin>>num;
                if(num>max)max=num;
                node *p=new node;
                p->e=num;
                node *q=head;
                for(int j=0;j<i;j++)q=q->next;
                q->next=p;
            }
            while(max/10){
                max/=10;
                weishu++;
            }
            weishu++;
            //display();
        }
        void displayData(){
            node *p=head->next;
            while(p){
                cout<<p->e<<" ";
                p=p->next;
            }
            cout<<endl;
            //cout<<weishu<<endl;
        }
    
        void init(){//将队头队尾指针设置成NULL
            for(int i=0;i<10;i++){
                f[i]=NULL;
                r[i]=NULL;
            }
        }
    
        void RadixSort(){
            int i; node* p;
            for(i=1;i<=weishu;i++){
                init();   //将队头队尾指针设置成NULL
    
                p=head->next; //开始一趟分配的过程
                while(p){
                    int w=( p->e /(int)pow(10,i-1))%10; //取得第i位的数据
                    if(f[w]==NULL)   f[w]=p; //若是该队列的第一个数据
                    else r[w]->next=p; //否则,在队尾插入
                    r[w]=p; //队尾指针指向新插入的数据
                    p=p->next;
                }
                p=head;   //开始一趟收集的过程
                for(int i=0;i<10;i++){  //共10个队列
                    if(f[i]){ //若第i个队列不空
                        p->next=f[i];
                        p=r[i];
                    }
                }
    
                p->next=NULL;  //收集结束,链表加上结束标志。
                displayQueue();
                displayData();
            }
            cout<<endl;
        }
    
    
        void displayQueue(){
            for(int i=0;i<10;i++){
                cout<<i<<":";
                if(f[i]==NULL)cout<<"NULL";
                else{
                    node *p=f[i];
                    while(p&&p!=r[i]){
                        cout<<"->"<<p->e;
                        p=p->next;
                    }
                    cout<<"->"<<r[i]->e<<"->^";
                }
                cout<<endl;
            }
        }
    };
    int main(){
        int t;
        cin>>t;
        while(t--){
            Sort test;
            test.RadixSort();
            //test.display();
        }
        return 0;
    }
    
    
    展开全文
  • 基数排序是由桶排序引申的算法,并且有可能突破NlogN的极限。
  • #include using namespace std; void quicksort(int a[],int low,int high) { int i,j,m; i = low; m = low; // m指向相同关键字部分的最右端 ... // 记录枢轴的值(枢轴有个)...=high) // 判断是否构成快速排序的条...
  • 快排的效率很快,但是我们很少知道如何利用它进行多关键字排序,比如我想对一个数组a[i][0]进行的一个元素进行主关键字排序,又想对a[i][1]进行次关键字排序。那么接下来就是解决这个问题的方法。 学过数据结构的...
  • 序言前几篇文章中我们分别介绍了JAVA数据结构和算法-简单排序之冒泡排序、JAVA数据结构和算法-简单排序之选择排序和JAVA数据结构和算法-简单排序之插入排序。在实际使用过程当中,很少会使用单一基础数据类型,更...
  • 数据结构-排序

    2015-10-17 18:08:00
    排序的稳定性如果i==j,且i在j前面,排序完成后i仍旧在j前面则这个排序算法是稳定... 2、交换: 数据元素之间需要交换才能得到预期结果 对于多关键字排序,只需要在比较操作时同时考虑多个关键字即可! 内排序 排序过...
  • 数据结构-基数排序

    2017-04-13 17:03:48
    基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。 分为:①多关键字排序,②链式基数排序两种 ①多关键字排序,还分为两种方法:一,最高位优先,二,最低位优先 下面是最低位优先的方法...
  • 排序7.1 基本概念7.2 插入排序7.3 交换排序7.4 选择排序7.5 归并排序7.6 分配排序7.7 各种内部排序比较7.1 基本概念...条记录具有相同的关键字若具有相同关键字的记录经过排序后记录的相对位置仍保持不变则该排序
  • 数据结构_排序

    2020-05-26 13:02:38
    从上面的例可以看出,关键字排序最终可以转换成单个关键字排序,故这里主要讨论单个关键字排序。 (1)排序的稳定性 也正是由于排序不仅是针对主关键字,那么对于次关键字,因为待排序的记录序列中可能...
  • 数据结构基础(15) --基数排序

    千次阅读 2015-01-11 10:57:22
    基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。实现多关键字排序通常有两种作法: 最低位优先法(LSD) 先对K[0]{基数的最低位}进行排序,并按 K(0) 的不同值将记录序列分成若干...
  • 稳定性:假定在待排序的记录序列中,存在个具有相同的关键字的记录,若经过排序,这些记录的相对次 序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排 ...
  • 链式基数排序(多关键字排序) 特点 排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序 它们的时间复杂度可达到线性阶:O(n)。 桶式排序 假设待排序的记录的值在0~m-1之间 设置m个桶, 依次扫描待...
  • 排序——数据结构

    2019-04-22 17:12:00
    排序的稳定性::假定在待排序的记录序列中,存在个具有相同的关键字的记录,若经过排序,这些记录的相对次 序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排 序后的序列中,...
  • 数据结构 内部排序 的思维导图

    千次阅读 2020-05-21 21:18:41
    目录 插入排序(直接插入、折半插入) 交换排序(起泡排序、快速排序) 选择排序(简单选择排序) 归并排序(归并排序) 基数排序(多关键字排序) 思维导图
  • 基数排序是一种借助多关键字排序的思想,对单逻辑关键字进行排序的方法。代码实现/* 基数排序 算法思想假设我有数据 11 23 45 29 31 67 59 32 假设我拥有10个桶,编号分别为0-9 一开始,我将个位数相应的数据都放入...
  • 分配类排序不需要比较关键字的大小,它是根据关键字中各位的值,通过对待排序记录进行若干趟 “ 分配 ” 与 “ 收集” 来实现排序的,是一种借助于多关键字排序的思想对单关键字排序的方法。基数排序(Radix Sorting)...
  • 首先排序的最简单定义是将“无序”的数据调整为“有序”的...很多时候我们会遇到多关键字排序的情况,比如有些学校在选择学生的时候会先看总分,总分相同的情况下重点关注数学成绩,这里的总分就是主关键字,数学...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,036
精华内容 414
关键字:

多关键字排序数据结构

数据结构 订阅