内部排序课件

10.2插入排序10.3快速排序10.4堆排序10.5归并排序10.6基数排序10.7各种排序方法的综合比较内部排序10.1概述本章小结习题十10.1概述一、排序的定义二、内部排序和外部排序三、内部排序方法的分类一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97

一般情况下，假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：

Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为

{Rp1,Rp2,

…，Rpn}的操作称作排序。二、内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；

反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。三、内部排序的方法

内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区

基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类

归并类其它方法待排记录的数据类型定义如下:#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项

InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置

intlength;//顺序表长度}SqList;//顺序表类型1.插入类

将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。2.交换类

通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。3.选择类

从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。4.归并类

通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。5.其它方法10.2插入排序直接插入排序表插入排序折半插入排序希尔排序2-路插入排序有序序列R[1..i-1]R[i]无序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]无序序列R[i+1..n]1.直接插入排序13

384965769727279776654938270123456713

384965769766977665493813012345676实现“一趟插入排序”可分三步进行：3．将R[i]插入(复制)到R[j+1]的位置上。2．将R[j+1..i-1]中的所有记录均后移一个位置；1．在R[1..i-1]中查找R[i]的插入位置，

R[1..j].key

R[i].key<R[j+1..i-1].key；从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i];//设置“哨兵”循环结束表明R[i]的插入位置为j+1R[0]jR[i]for(j=i-1;R[0].key<R[j].key;--j);//从后往前找j=i-1插入位置

对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；for(j=i-1;R[0].key<R[j].key;--j);

R[j+1]=R[j]R[0]jR[i]j=i-1上述循环结束后可以直接进行“插入”插入位置令i=2，3，…,n,实现整个序列的排序。for(i=2;i<=n;++i)

if(R[i].key<R[i-1].key)

{在

R[1..i-1]中查找R[i]的插入位置;

插入R[i];

}voidInsertionSort(SqList&L){//对顺序表L作直接插入排序。

for(i=2;i<=L.length;++i)

if(L.r[i].key<L.r[i-1].key){

}}//InsertSortL.r[0]=L.r[i];//复制为监视哨L.r[i]=L.r[i-1];for(j=i-2;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；对于直接插入排序：最好的情况（关键字在记录序列中顺序有序(正序））：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：0“移动”的次数：“移动”的次数：时间复杂度为：O（n2)

因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。2.折半插入排序14364952805861239775ilowhighmmlowlowmhigh14364952586180239775ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.rvoidBiInsertionSort(SqList&L){}//BInsertSort在L.r[1..i-1]中折半查找插入位置；for(i=2;i<=L.length;++i){}//forL.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入low=1;high=i-1;while(low<=high){}m=(low+high)/2;//折半if(L.r[0].key<L.r[m].key)

high=m-1;//插入点在低半区elselow=m+1;//插入点在高半区3.2_路插入排序4938659776132749初始关键字：基本思想：……排序过程中d的状态：i=149firstfinal4938firstfinali=2496538firstfinali=349659738firstfinali=4...49657697132738firstfinali=74949657697132738firstfinali=84.表插入排序

为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。#defineSIZE100//静态链表容量typedefstruct{RcdTyperc;//记录项

intnext;//指针项}SLNode;

//表结点类型typedefstruct{

SLNoder[SIZE];//intlength;}SLinkListType;//静态链表类型初始状态：MAXINT493865977613274910-------.Key.nextMAXINT4938659776132749201------.Key.nextMAXINT49386597761327492310-----.Key.nextMAXINT493865977613274923140----.Key.nextMAXINT4938659776132749231504---.Key.nextMAXINT49386597761327496315042--.Key.nexti=2i=3i=4i=5i=6

012345678MAXINT493865977613274963150472-.Key.nextMAXINT4938659776132749681504723.Key.nexti=7i=8012345678voidLInsertionSort(SLinkListTypeSL){//对记录序列SL.r[1..n]作表插入排序

SL.r[0].key=MAXINT;SL.r[0].next=1;SL.r[1].next=0;

for(i=2;i<=n;++i)for(j=0,k=SL.r[0].next;SL.r[k].key<=

SL.r[i].key;j=k,k=SL.r[k].next);

{SL[j].next=i;SL[i].next=k;}//结点i插入在结点j和结点k之间}//LinsertionSort算法中使用了三个指针：其中：p指示第i个记录的当前位置

i指示第i个记录应在的位置

q指示第i+1个记录的当前位置如何在排序之后调整记录序列？MAXINT4938659776132749681504723.Key.next初始状态：

012345678MAXINT13386597764927496(6)1504823.Key.nextMAXINT1327659776493849667504813.Key.nexti=1;p=6i=2;p=7MAXINT4938659776132749681504723.Key.next初始状态：

012345678MAXINT13386597764927496(6)1504823.Key.nextMAXINT1327659776493849667504813.Key.nexti=1;p=6i=2;p=7MAXINT1327389776496549667704853.Key.nexti=3;p=(2),7i=4;p=(1),6MAXINT1327384976956549667764053.Key.next…….voidArrange(SLinkListTypeSL){p=SL.r[0].next;//p指示第一个记录的当前位置

for(i=1;i<n;++i){

while(p<i)p=SL[p].next;

q=SL[p].next;//q指示尚未调整的表尾

if(p!=i){

SL[p]←→SL[i];//交换记录，使第i个记录到位

SL[i].next=p;//指向被移走的记录

}

p=q;//p指示尚未调整的表尾，

//为找第i+1个记录作准备

}}//Arrange5.希尔排序（又称缩小增量排序）

基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。

所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：

将记录序列分成若干子序列，分别对每个子序列进行插入排序。其中，d

称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n个记录分成d个子序列：

{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}

…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}取d3=1三趟分组：1327485544938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分组：49

38

65

97

76

13

27

48

55

4取d2=3二趟分组：13

27

48

55

4

49

38

65

97

7612345678910voidShellSort(SqList&L,intdlta[],intt){//增量为dlta[]的希尔排序

for(k=0;k<t;++t)

ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序}//ShellSortvoidShellInsert(SqList&L,intdk){

//对有序表L作一趟希尔排序，

for(i=dk+1;i<=L.length;i++){

//将每个元素插入在自己的子表中

L.r[0]=L.r[i];j=i-dk;while(j>0&&L.r[0].key<L.r[j].key)

{L.r[j+dk]=L.r[j];j=j-dk;}

L.r[j+dk]=L.r[0];//插入

}//for}//ShellInsert

10.3快速排序(借助交换）1、起泡排序2、一趟快速排序3、快速排序4、快速排序的时间分析1.起泡排序基本思想：将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。

一般地：第i趟排序是对前n-i+1进行冒泡排序，使第i个大关键字元素放在第n-i+1的位置上——第i趟冒泡排序.

重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止——结束条件例4938659776132730

初始关键字3849657613273097

第一趟结果38496513273076

第二趟结果384913273065

第三趟结果3813273049

第四趟结果13273038

第五趟结果384976971397279730971376767627301365276530651313494930492738273830381234567813273038

第六趟结果voidBubbleSort(Sqlist&L){n=L.length;flag=0;//flag=0;表明还有必要进行排序

for(i=1;（i<n)&&!flag;i++)

}//BubbleSortflag=1;//假设有序for(j=1;j<i;j++)if(L.r[j]>L.r[j+1]){L.r[j]↔L.r[j+1];

flag=0;//假设不成立

}

性能分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡“比较”的次数：0“移动”的次数：“移动”的次数：n-1时间复杂度为：O（n2)2、一趟快速排序（一次划分）

基本思想：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且

R[j].key≤R[i].key≤R[j].key(s≤j≤i-1)

枢轴

(i+1≤j≤t)。

4938659776132749初始关键字：

012345678

完成一趟排序：(273813)49(76976549)

稳定性问题：不稳定！4938496597761327

完成一趟排序：(27384913)49(769765)

intPartition(SqList&L,intlow,inthigh){//一次划分}//PartitionL.r[0]=L.r[low];pivotkey=L.r[low].key;//枢轴while(low<high){}while(low<high&&L.r[high].key>=pivotkey)--high;//从右向左搜索L.r[low]=L.r[high];while(low<high&&R[low].key<=pivotkey)++low;

//从左向右搜索L.r[high]=L.r[low];R[low]=R[0];

returnlow;3、快速排序

首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序void

QSort(SqList&L,intlow,inthigh)

{

//对记录序列L.r[s..t]进行快速排序

if(low<high){//长度大于1

}}//QSortpivotloc=Partition(L,low,high);//对L.r[low..high]进行一次划分QSort(L,low,pivotloc-1);

//对低子序列递归排序，pivotloc是枢轴位置QSort(L,pivotloc+1,high);

//对高子序列递归排序voidQuickSort(SqList

&L){

//对顺序表进行快速排序

QSort(L,1,L.length);}//QuickSort

第一次调用函数Qsort时，待排序记录序列的上、下界分别为1和L.length。4、快速排序的时间分析假设一次划分所得枢轴位置i=k，则对n个记录进行快排所需时间：其中Tpass(n)为对n个记录进行一次划分所需时间。

若待排序列中记录的关键字是随机分布的，则k

取1至n

中任意一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)设Tavg(1)≤b则可得结果：结论:快速排序的时间复杂度为O(nlogn)由此可得快速排序所需时间的平均值为：

若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。

为避免出现这种情况，需在进行一次划分之前，进行“预处理”，即：

先对L.r[low].key,R[high].key和L.r[

(s+t)/2].key，进行相互比较，然后取关键字为

“三者之中”的记录为枢轴记录。10.4选择排序简单选择排序堆排序1、简单选择排序基本思想：第i趟排序是，在n-i+1个元素中选择一个最小的放在第i个位置上（1≤i≤n-1),共需要n-1趟。有序序列R[1..i-1]无序序列R[i..n]

第i趟简单选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列R[i+1..n]例初始：[49386597761327]kjjjjjjkki=11349一趟：13[386597764927]i=2kkjjjjj2738二趟：13

27[6597764938]三趟：13

27

38[97764965]四趟：13

27

38

49[769765]五趟：13

27

38

49

65[9776]六趟：13

27

38

49

65

76[97]排序结束：13

27

38

49

65

76

97稳定性问题：不稳定！4938274913例：27384949简单选择排序的算法描述如下：voidSelectSort(SqList&L){

//对记录序列L.r[1..n]作简单选择排序。

for(i=1;i<n;++i){

//选择第i个小的记录，并交换到位

}}//SelectSortk=i;for(j=i+1;j<=n;j++)if(L.r[j].key<L.r[k].key)k=j;

//在R[i..n]中选择关键字最小的记录if(k!=i)L.r[i]↔L.r[k];

//与第i个记录交换时间性能分析:

对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为：

移动记录的次数，最小值为0,

最大值为3(n-1),即每一趟都交换。2、堆排序堆的定义:n个元素的序列{k1,k2,……,kn}，当且仅当满足下列关系时，称之为堆。或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1例（96，83，27，38，11，9）例（13，38，27，50，76，65，49，97）962791138831327384965765097大顶堆小顶堆堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫~。堆排序需解决的两个问题：1.如何由一个无序序列建成一个堆？2.如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第二个问题解决方法——筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”例13273849657650979727384965765013输出：132749389765765013输出：13所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。堆堆筛选9749382765765013输出：13273849502765769713输出：13276549502738769713输出：1327384965502738769713输出：1327387665502738499713输出：132738495065762738499713输出：132738499765762738495013输出：13273849506597762738495013输出：13273849509765762738495013输出：1327384950657665972738495013输出：1327384950659765762738495013输出：13273849506576输出：132738495065769798814973556412362740例如:是大顶堆12但在98和12进行互换之后，它就不是堆了，因此，需要对它进行“筛选”。98128173641298比较比较建堆是一个从下往上进行“筛选”的过程。40554973816436122798例如:排序之前的关键字序列为123681734998817355

现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。98494064361227voidHeapSort(HeapType&H){

//对顺序表H进行堆排序}//HeapSortfor(i=H.length/2;i>0;--i)//把H.r[i..H.length]建成大顶堆

HeapAdjust(H.r,i,H.length);

//建大顶堆for(i=H.length;i>1;--i){H.r[1]↔H.r[i];

//将堆顶记录和当前未经排序子序列

//H.r[1..i]中最后一个记录相互交换

HeapAdjust(H.r,1,i-1);

//对H.r[1]进行筛选}voidHeapAdjust(HeapType&H,ints,intm){//已知H.r[s..m]中记录的关键字除H.r[s]之外均

//满足堆的特征，本函数自上而下调整H.r[s]的

//关键字，使H.r[s..m]也成为一个大顶堆}//HeapAdjustrc=H.r[s];//暂存H.r[s]for(j=2*s;j<=m;j*=2){//j初值指向左孩子自上而if

(j<m&&H.r[j].key<H.r[j+1].key)++j;//下的筛选过程;if

(rc.key>=R[j].key)

break;H.r[s]=H.r[j];s=j;}H.r[s]=rc;

//将调整前的堆顶记录插入到s位置if

(rc.key>=R[j].key)

break;//再作“根”和“子树根”之间的比较，

//若“>=”成立，则说明已找到rc

的插

//入位置s，不需要继续往下调整R[s]=R[j];s=j;

//否则记录上移，尚需继续往下调整if

(j<m

&&R[j].key<R[j+1].key)++j;//左/右“子树根”之间先进行相互比较

//令j指示关键字较大记录的位置堆排序的时间复杂度分析：1.对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；3.调整“堆顶”n-1

次，总共进行的关键字比较的次数不超过

2(

log2(n-1)

+

log2(n-2)

+…+log22)<2n(

log2n

)因此，堆排序的时间复杂度为O(nlogn)。2.对

n

个关键字，建成深度为h(=

log2n+1)的堆，

所需进行的关键字比较的次数至多4n；堆排序是一和不稳定的排序方法!10.5归并排序基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列。2-路归并排序排序过程:1)设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。2)两两合并，得到n/2个长度为2或1的有序子序列。3)再两两合并，……如此重复，直至得到一个长度为n的有序序列为止。例:初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行

log2n

趟。空间复杂度：S(n)=O(n)算法描述：（非递归）voidmergesort(RcdTyper[],intn)

//对r进行归并排序，r中有n个元素{s=1;

//初始归并段长度s为1while(s<n){tgb(s,n,r,t);//一趟归并，t是和r同类型的中间量

s*=2;if(s<n){tgb(s,n,t,r);s*=2;}//t到relse{i=1;//将t中的放回r中

while(i<=n)r[i]=t[i++];}}}递归算法：voidtgb(ints,intn,RcdTyper[],RcdTypet[]){//一趟归并，归并段的长度为si=1;while(i<=(n-2*s+1))//完整的两个段归并

{merge(r,t，i,i+s-1,i+2*s-1);i=i+2*s;}if(i<(n-s+1))merge(r,t,i,i+s-1,n);//后一个段不足s个元素

else//后一个段不存在

while(i<=n)t[i]=r[i++];}voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){

//将有序的记录序列SR[i..m]和SR[m+1..n]//归并为有序的记录序列TR[i..n]}//Mergefor(j=m+1,k=i;i<=m&&j<=n;++k){//将SR中记录由小到大地并入TRif(SR[i].key<=SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];

//将剩余的SR[i..m]复制到TRif(j<=n)TR[k..n]=SR[j..n];

//将剩余的SR[j..n]复制到TR

在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]这个操作对顺序表而言，是轻而易举的。voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){

//将有序的记录序列SR[i..m]和SR[m+1..n]//归并为有序的记录序列TR[i..n]}//Mergefor(j=m+1,k=i;i<=m&&j<=n;++k){//将SR中记录由小到大地并入TRif(SR[i].key<=SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];

//将剩余的SR[i..m]复制到TRif(j<=n)TR[k..n]=SR[j..n];

//将剩余的SR[j..n]复制到TR归并排序的算法如果记录无序序列R[s..t]的两部分

R[s..

(s+t)/2

]和R[

(s+t)/2+1..t]分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。

由此，应该先分别对这两部分进行2-路归并排序。例如：52,23,80,36,68,14(s=1,t=6)[52,23,80][36,68,14][52,23][80][52][23,52][

23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]void

Msort(RcdTypeSR[],RcdType&TR1[],ints,intt)

{

//将SR[s..t]归并排序为TR1[s..t]if(s==t)TR1[s]=SR[s];else{

m=(s+t)/2;

//将SR[s..t]平分为SR[s..m]和SR[m+1..t]Msort(SR,TR2,s,m);//递归地将SR[s..m]归并为

//有序的TR2[s..m]Msort(SR,TR2,m+1,t);//递归地SR[m+1..t]归并为有

//序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);

//将TR2[s..m]和TR2[m+1..t]//归并到TR1[s..t]}}//Msort……voidMergeSort(SqList&L){//对顺序表L作2-路归并排序

MSort(L.r,L.r,1,L.length);}//MergeSort

容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行

log2n

趟。10.6基数排序多关键字排序：例对52张扑克牌按以下次序排序：2<3<……<A<

2<

3<……<

A<

2<

3<……<

A<2<3<……<A两个关键字：花色（<

<

<）面值（2<3<……<A）并且“花色”地位高于“面值多关键字排序方法：最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列(要求稳定的排序方法）MSD与LSD不同特点按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序链式基数排序基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法链式基数排序：用链表作存储结构的基数排序链式基数排序步骤：1）设置10个队列，f[i]和e[i]分别为第i个队列的头指针和尾指针2）第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同3）第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表4）重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列例初始状态：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集：算法评价时间复杂度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd))其中：n——记录数

d——关键字数

rd——关键字取值范围空间复杂度：S(n)=2rd个队列指针+n个指针域空间初始状态：127810906393058918450526900808302345678910f[0]=0e[0]=0f[1]=0e[1]=0f[2]=0e[2]=0f[3]=0e[3]=0f[4]=0e[4]=0f[5]=0e[5]=0f[6]=0e[6]=0f[7]=0e[7]=0f[8]=0e[8]=0f[9]=0e[9]=011223344566778910493006308318450527800810958926903106719258f[0]=0e[0]=0f[1]=0e[1]=0f[2]=0e[2]=0f[3]=0e[3]=0f[4]=0e[4]=0f[5]=0e[5]=0f[6]=0e[6]=0f[7]=0e[7]=0f[8]=0e[8]=0f[9]=0e[9]=013447791049300630831845052780081095892690310671925831016258750500810993006326927808318458909243811065二趟收集：一趟收集750500810993006326927808318458909243811065f[0]=0e[0]=0f[1]=0e[1]=0f[2]=0e[2]=0f[3]=0e[3]=0f[4]=0e[4]=0f[5]=0e[5]=0f[6]=0e[6]=0f[7]=0e[7]=0f[8]=0e[8]=0f[9]=0e[9]=04479287928900806308310918426927850558993003102681754三趟收集：311065二趟收集：算法描述：P288一、时间性能1.平均的时间性能基数排序时间复杂度为O(nlogn)：快速排序、堆排序和归并排序时间复杂度为O(n2)：直接插入排序、起泡排序和简单选择排序时间复杂度为O(n):10.7各种排序方法的综合比较2.当待排记录序列按关键字顺序有序时3.

简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能蜕化为O(n2)。二、空间性能指的是排序过程中所需的辅助空间大小1.所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；2.

快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；3.

归并排序所需辅助空间最多，其空间复杂度为O(n);4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。三、排序方法的稳定性能1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。2.当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。排序之前:{·