三九宝宝网宝宝百科宝宝知识

C++基础RadixSort基数排序

11月12日 编辑 39baobao.com

[C++技巧:OpenCASCADE智能指针的使用]学习OCC的第一步是要了解其类的结构及组成,比如AIS_InteractiveObject类用来表示一个交互 式图形对象,如果进一步了解会发现其继承关系是:MMgt_TShared->Standard_Transient->P...+阅读

基本思想

实现排序主要是通过关键字间的比较和移动记录这两种操作,而实现基数排序不需要进行记录关键字间的比较,它是一种利用多关键字排序的思想,即借助"分配"和"收集"两种操作对单逻辑关键字进行排序的方法。

基数排序的方法是:一个逻辑关键字可以看成由若干个关键字复合而成的,可把每个排序关键字看成是一个d元组:

例如,如果关键字是数值,且其值在0

99范围内,则可把每一个十进制数字看成是一个关键字,即可认为K由2个关键字(K0,K1)组成,其中K0是十位数,K1是个位数。排序时先按 的值从小到大将记录分配到r个盒子中,然后依次收集这些记录,考试大提示:再按 的值分配到r个盒子中,如此反复,直到对分配后收集起来的序列,便是完全排序的状态,其中r称为基数。这个过程是按LSD(最低位优先法)进行排序的,即从最低数位关键字起,按关键字的不同值对序列中记录" 分配"和"收集"的。基数的选择和关键字的分解法因关键字的类型而异。

为了实现记录的"分配"和"收集",需设立r个队列,排序前将队列设置为空,分配时,将记录插入到各自的队列中去,收集时将这些队列中记录排在一起。

一般采用静态链表作为记录序列的存储结构,并且不另外设置各链队列的结点空间,而是利用静态链表中的结点作为链队列中的结点,这样只需修改指针即可完?quot;分配"和"收集"任务。时间复杂度为O(d(n+rd))

在基数排序算法中,没有进行关键字的比较和记录的移动,Examda提示:而只是顺链扫描链表和进行指针赋值,所以,排序的时间主要耗费在修改指针上。

对于n个记录(假设每个记录含d个关键字,每个关键字的取值范围为rd个值)进行一趟分配的时间复杂度为O(n),进行一趟收集的时间复杂度为O(rd),整个排序过程需要进行 d趟分配和收集操作。因此,链式基数排序总的时间复杂度为O(d(n+rd))。

当n较小,d较大时,基数排序并不合适。只有当n较大,d较小时,特别是记录的信息量较大时,基数排序最为有效。基数排序中所需辅助空间为2rd个队列指针,另外每个记录中都增加了一个指针域。

&emspinclude

&emspinclude

using namespace std;

constant size must be defined as the array size for bucketSort to work

const int SIZE = 12;

void bucketSort( int [] );

void distributeElements( int [], int [][ SIZE ], int );

void collectElements( int [], int [][ SIZE ] );

int numberOfDigits( int [], int );

void zeroBucket( int [][ SIZE ] );

int main()

{

int array[ SIZE ] = { 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21 };

cout

以下为关联文档:

法语基数词与序数词1.Salutation ment a va?你好吗? a ne peut pas aller mieux.好得不得了 a boume?近来很得意吧? quoi de neuf?近来可好? alors,t'es toujours vivant?哇塞,你还活着啊? a roule?...

VC++字体通用的类#include "stdafx.h" #include "font.h" COleFont properties CString COleFont::GetName() { CString result; GetProperty(0x0, VT_BSTR, (void*) return result; } void...

C++技巧:emacs完美的C++的自动补全1,CVS cedet的最新代码,1.04代码补全很慢。 cvs -z3 -d:pserver:anonymous#cedet.cvs.sourcefe.:/cvsroot/cedet co -P cedet 2,命令行运行 touch `find -name "Makefile"` (注...

解决VC++程序国际化的类,解决乱码问题#include "stdafx.h" #include "global.hpp" Deion: generate an error message int Error(long err, char *fmt, ...) { static char buf[256]; static char buf2[256]; va...

使用VC++6关闭指定窗口标题的程序常常听说有病毒关闭杀毒软件,是枚举窗口标题来实现的,那么内幕是什么呢? 其实只需要数10行代码就可以了。 VC++6.0建立Win32 APPlication,复制下面的代码... #include BOOL CALL...

C++中使用断点写调试方法C/C++ code: f9 --- 设置/取消断点 f10 --- 单步执行 f11 --- 比f10的步幅小,f10在函数的调用时,直接跳过,在f11下,会进入函数体! f5 --- 执行到下一个断点! 了解调试,首先要知道"...

c++读写剪贴板代码代码如下: 写: if(OpenClipboard()) { CString str; HANDLE hClip; char *pBuf; EmptyClipboard(); str="879789789"; hClip=GlobalAlloc(GMEM_MOVEABLE,str.GetLength()+1);...

c++数据类型及复杂声明推演数据类型 c++程序员已经知道c语言有五种数据类型:void,int,float,double和char: 类型 描述 void 无数据类型 int 整数类型 float 浮点数 double 双精度浮点数 char 字符型 c+...

C++基础:有趣的#define的一个实例看了一下google CoverStory的代码,有一个地方很有意思: These are the various document types used by CoverStory. Included in both Obj-C and plist sources. A little ma...

推荐阅读
图文推荐