`
java-mans
  • 浏览: 11339579 次
文章分类
社区版块
存档分类
最新评论

数据结构课程设计----基数排序

 
阅读更多

一、基数排序的基本思想:排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

二、最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。
最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。

分享到:
评论

相关推荐

    数据结构课程设计--十种内部排序发的比较

    各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或者大概执行时间。通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。

    数据结构实验报告--多关键字排序.doc

    基数排序又称桶排序,从关键字本身加以分析,充分的利用关键字的特点。在基数排序中,不需要关键字间的比较。基数排序是一个分配,收集的过程,因为此实验关键字被分为十位和个位的二元组,所以需要分配,收集两次。...

    数据结构课程设计多种排序算法时间比较.c

    快速排序,基数排序,插入排序,希尔排序,堆排序,归并排序等算法对数排序的时间进行比较。可以对5000000以内(超大数据量)的随机数(可能存在超大数值)进行排序!!!

    数据结构课程设计(三)

    各种排序时间在不同情况下的时间消耗 测试 直接插入排序,折半插入排序,希尔排序,冒泡排序,双向冒泡排序,快速排序,简单选择排序,堆排序,基数排序排序算法,在不同的数据测试下(数据量的多少和数据的大小...

    数据结构课程设计C语言版

    C语言版课程设计 #include #include <ctime> 产生随机数 #include <windows.h> 调用计算时间的函数 #include using namespace std; 产生随机数,输入产生随机数的个数,范围,即可产生待排数据 void Random(long ...

    数据结构课设 各种排序

    1、链表排序 [问题描述] 建立一个...设计要求:利用随机函数产生10个样本,每个样本有20000随机整数,利用直接插入排序、希尔排序,冒泡排序、快速排序、选择排序、堆排序,归并排序,基数排序八种排序方法进行排序

    数据结构课程设计.zip

    基数排序。 (2)待排序表的表长不少于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字移动次数(关键字交换计为3次移动)。

    数据结构_排序

    插入排序、交换排序、选择排序、归并排序、基数排序 各种内排序方法的比较和选择

    用stl实现基数排序算法

    用STl实现基数排序算法 功能强大非常适合数据结构课程设计

    汽车牌照的排序与查找问题-数据结构与算法课程设计报告

    此程序要完成如下要求:选择一种数据结构来存储每个车辆的信息(如车主姓名,汽车等),在此基础上进行基数排序,而汽车牌照是由汉字、字母以及数字组成,即多关键字,其中字母和数字的比较是比较容易实现的,考虑到...

    北大数据结构代码

     课程的总目标是学生将基本掌握数据结构和算法的设计分析技术,提高程序设计的质量;根据所求解问题的性质选择合理的数据结构并对时间空间复杂性进行必要的控制。具体包括如下几个方面: 1. 熟练掌握包括线性表...

    数据结构与算法课程设计——航班查询系统

    1.1课程设计选题 4 1.1.1选题描述 4 1.1.2选题要求 4 第二章 系统需求分析 4 2.1输入/输出形式和输出值 4 2.2功能需求 4 2.3数据流图 5 2.4 用户特点 5 2.4 假定和约束 5 第三章 概要设计 5 3.1设计思想 5 3.2基本...

    77G 22套C语言 C++ 数据结构 程序设计视频课程合集 C丨C++相关学习视频全套视频教程

    基数排序.mp4 21.树.mp4 22.二叉树的存储表示与实现.mp4 23.二叉树的遍历.mp4 24.二叉查找树.mp4 25.红黑树.mp4 26.堆.mp4 27.堆排序.mp4 28.哈希表.mp4 29.图_邻接矩阵.mp4 30.邻接表.mp4 31.图_深度...

    内部排序算法的实现与比较-C语言

    数据结构课程设计,从折半插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、二路归并排序、基数排序等排序方法中选用5种,实现数据的排序。

    航班信息的查询与检索(数据结构课设)

    对于本设计,可采用基数排序法对一组具有结构特点的飞机航班号进行排序,利用二分查找法对排好序的航班记录按航班号实现快速查找,按其他次关键字的查找可采用最简单的顺序查找方法进行,因此他们用得较少。...

    数据结构(C++)有关练习题

    <br>实验四 综合(课程设计) 内容及步骤: 1、假定一维数组a[n]中的每个元素值均在[0,200]区间内,用C++编写一个算法,分别统计出落在[0,20],[21,50],[51,80],[81,130],[131,200]等各区间内的元素...

    严蔚敏:数据结构题集(C语言版)

    《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参考教材。本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论查找和排序的...

    数据结构(C语言版)[严蔚敏]

    《数据结构》(c语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。学了数据结构后,许多以前写起来很繁杂的代码现在写起来很清晰明了. 本书的前半部分从抽象数据类型的...

    《数据结构》(C语言版)严蔚敏

    《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。学了数据结构后,许多以前写起来很繁杂的代码现在写起来很清晰明了. 本书的前半部分从抽象数据类型的...

    [数据结构(C语言版)].严蔚敏_吴伟民.高清扫描版.rar

    《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。 本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论查找和...

Global site tag (gtag.js) - Google Analytics