编程入门教程第十章 排序 - 图文

第十章排序10.1排序的基本概念

10.2简单排序方法（复杂度O(n2)）

10.3先进排序方法（复杂度O(nLogn)/O(n3/2)）10.4基数排序（复杂度O(d×n)）10.5各种排序的综合比较http://www.shuiqiangushi.cn/

ypb@ustc.edu.cn1中国科学技术大学10.1排序的基本概念?排序单元结构定义

typedefintKeyType;//简单起见，只要可比就可以typedefstruct{

KeyTypekey;InfoTypeotherinfo;

}RcdType;

?例：

Typedefstruct{

charname[10];charsex[2];charbirthday[8];chardepartment[4];}InfoType

ypb@ustc.edu.cn2中国科学技术大学?排序

设N个记录{r1,r2…rn}，相应关键字{k1,k2…kn}求一种排列p1,p2…pn，使得kp1≤kp2≤…≤kpn即{rp1,rp2…rpn}是按关键字有序序列

?稳定与不稳定排序

若ki=kj,并且在待排序列中ri领先于rj(即i

?内部排序与外部排序

内部排序：仅在内部存储器中完成的排序

外部排序：在排序中需要访问外部存储器的排序

?本章排序操作对象：Typedef struct{

RcdType r[MAXSIZE+1];Intlength;}Sqlist;

3中国科学技术大学ypb@ustc.edu.cn10.2简单排序方法（复杂度O(n2)）10.2.1选择排序

voidSelectPass（Sqlist&L,inti）复杂度O(n)voidSelectSort（Sqlist&L）复杂度O(n2)

–n(n＋1)/2次比较和3（n-1）次交换。

–本身是稳定算法，本例由交换引起不稳定，可采用移动策略获稳定算法

R[i]R[j]

有序序列R[1..i-1]无序序列R[i..n]有序序列R[1..i] 无序序列R[i+1..n] ypb@ustc.edu.cn4中国科学技术大学