计算机软件技术基础 第3版 课件 第7章 排序

第7章内部排序2本章主要内容7.1排序的基本思想和基本概念7.2内部排序的主要算法及时空效率分析7.3内部排序实例237.1排序的基本思想和基本概念被排序对象通常为文件，即一组记录关键字排序的稳定性针对具有多个相同关键字的记录排序文件的常用存储方式顺序表链表34顺序存储方式表示形式#defineMAXSIZE1000

//待排顺序表最大长度typedefstruct{KeyTypekey;

otherTypeinfo;}RecordType;typedefstruct{RecordTyper[MAXSIZE+1];

//r[0]闲置

intn;

//顺序表长度}SqList;45内部排序与外部排序排序算法性能评价时间复杂度空间复杂度57.2内部排序的主要算法及时空效率分析7.2.1直接插入排序7.2.2希尔排序7.2.3冒泡排序7.2.4直接选择排序7.2.5归并排序7.2.6快速排序7.2.7堆排序677.2.1直接插入排序不断地将无序子序列中的记录“插入”到有序序列中，从而逐渐地增加有序子序列的长度，直到所有记录都进入有序序列中为止。直接插入排序基本思想直接插入排序过程原始数据(23,10,20,36,40,13,27,11)8

(23,10,20,36,40,13,27,11)

i=2(10,23,20,36,40,13,27,11)

i=3(10,20,23,36,40,13,27,11)

i=4(10,20,23,36,40,13,27,11)

i=5(10,20,23,36,

40,13,27,11)

i=6(10,13,

20,23,36,

40,27,11)

i=7(10,13,

20,23,27,36,

40,11)

i=8(10,11,13,

20,23,27,36,

40)i=19直接插入排序思路假定待排序数据为L9有序序列L.r[1..i-1]L.r[i]无序序列

L.r[i..n]有序序列L.r[1..i]无序序列

L.r[i+1..n]10直接排序算法结构for(i=2;i<=L.n;i++){

将L.r[i]插入到由1..i-1

记录组成的有序序列中}101.确定插入位置；2.移动记录；3.插入；11“一趟”插入分三步进行1．在L.r[1]至L.r[i-1]中查找L.r[i]的插入位置

L.r[j].keyL.r[i].key<L.r[j+1].key2．将L.r[j+1]至L.r[i-1]中的所有记录均后移一个位置；3．将L.r[i]

插入到L.r[j+1]的位置上。1112确定插入位置L.r[0]=L.r[i];//设置“哨兵”循环结束表明L.r[i]的插入位置为j+1jL.r[0]L.r[i]while(L.r[0].key<L.r[j].key)

//从后往前找j=i-1插入位置13寻找插入位置与移动数据13jj=i-1L.r[0]L.r[i]插入位置L.r[0]=L.r[i];j=i-1;while(L.r[0].key<L.r[j].key){ L.r[j+1]=L.r[j]; j--;}14直接插入算法voidInsertSort(SqList&L){//对顺序表L作直接插入排序

for(i=2;i<=L.n;i++){

L.r[0]=L.r[i]; j=i-1; while(L.r[0].key<L.r[j].key){ L.r[j+1]=L.r[j]; j--; } L.r[j+1]=L.r[0];

}}定义：一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。引入哨兵后使得测试查找循环条件的时间大约减少了一半。算法中引进的L.r[0]

就是哨兵。哨兵有两个作用：①进人查找(插入位置)循环之前，它保存了L.r[i]的副本，使不致于因记录后移而丢失L.r[i]的内容；②它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为L.r[0].key和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。

直接插入排序——哨兵的作用

最好情况（原始记录按关键字有序排列）：O（n）“比较”的次数：最坏情况（原始记录按关键字逆序排列）：O（n2）“比较”的次数：0“移动”的次数：“移动”的次数：结论：适用原始数据基本有序或数据量不大的情况。直接插入排序——性能分析

希尔排序（Shell’smethod）又称为“缩小增量排序”，其基本思想是：

先取一个小于n的整数d1并作为第一个增量，将文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；

然后取第二个增量d2<d1，重复上述的分组和排序，直至所取的增量dt=1(dt<dt

1<…<d2<d1)为止，此时，所有的记录放在同一组中进行直接插入排序。1.希尔插入排序——算法思想

7.2.2希尔排序设待排序共有10个记录，其关键字分别为47,33,61,82,71,11,25,47

,57,02，增量序列取值依次为5,3,1。

2.希尔插入排序——过程

希尔排序实质上还是一种插入排序，其主要特点是：每一趟以不同的增量进行排序。在每趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，所以关键字较小的记录在排序过程中是作跳跃式的移动。另外，由于开始时增量的取值较大，每组中记录较少，故排序比较快，随着增量值的逐步变小，每组中的记录逐渐变多，但由于此时记录已基本有序了，因次在进行最后一趟增量为1的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。如何选择增量序列才能产生最好的排序效果，这个问题至今没有得到解决。希尔本人最初提出取d1=

n/2

，di+1=

di/2

，dt=1，t=

log2n

。3.希尔插入排序——特点

希尔排序比直接插入排序的平均性能要好：在最好情况（原始记录按关键字有序排列）下，移动次数为0，比较次数界于n～n2

之间。在最坏情况（原始记录按关键字逆序排列）下，移动次数和比较次数接近n2。在平均情况下，移动次数和比较次数在O（n1.3）左右，好于直接插入排序。4.希尔插入排序——性能效率7.2.3冒泡排序冒泡排序思想(1)：从后向前扫描数据，通过交换依次保证相邻两个数据有序。冒泡排序思想(2)：从前向后扫描数据，通过交换依次保证相邻两个数据有序。冒泡排序过程(1)原始数据(49,38,65,97,76,13,27,49)i=113,(49,38,65,97,76,27,49)i=213,27,(49,38,65,97,76,49)i=313,27,38,(49,49,65,97,76)i=413,27,38,49,(49,65,76,97)i=513,27,38,49,49,(65,76,97)i=613,27,38,49,49,65,(76,97)i=713,27,38,49,49,65,76,(97)未交换冒泡排序算法(1)voidBubbleSort(SqList&L){inti,j;intexchange;//交换标志

for(i=1;i<L.n;i++){//最多做n-1趟排序

exchange=0;//本趟排序开始前，交换标志应为假

for(j=L.n-1;j>=i;j--)//对无序区自下向上扫描

if(L.r[j+1].key<L.r[j].key){//交换记录

L.r[0]=L.r[j+1];//L.r[0]仅做暂存单元

L.r[j+1]=L.r[j]; L.r[j]=L.r[0]; exchange=1;//发生了交换，故将交换标志置为真

} if(!exchange)//本趟排序未发生交换，提前终止算法

return;}//endfor(外循环)}冒泡排序过程(2)原始数据(49,38,65,97,76,13,27,49)i=1(38,49,65,76,13,27,49,)97i=2(38,49,65,13,27,49,)76,97i=3(38,49,13,27,49,)65,76,97i=4(38,13,27,49,)49,65,76,97i=5(13,27,38,)49,49,65,76,97i=6(13,27,)38,49,49,65,76,97i=713,27,38,49,49,65,76,(97)未交换冒泡排序算法(2)voidBubbleSort(SqList&L){inti,j;intexchange;//交换标志

for(i=1;i<L.n;i++){//最多做n-1趟排序

exchange=0;//本趟排序开始前，交换标志应为假

for(j=1;j<=L.n-i;j++)//对无序区自下向上扫描

if(L.r[j].key>L.r[j+1].key){//交换记录

L.r[0]=L.r[j];//L.r[0]仅做暂存单元

L.r[j]=L.r[j+1]; L.r[j+1]=L.r[0]; exchange=1;//发生了交换，故将交换标志置为真

} if(!exchange)//本趟排序未发生交换，提前终止算法

return;}//endfor(外循环)}最好情况（记录按关键字有序排列）：只需进行一趟冒泡“比较”的次数：最坏情况（记录按关键字逆序排列）：需进行n-1趟冒泡“比较”的次数：0“移动”的次数：“移动”的次数：n-17.3.1冒泡排序——性能分析7.2.4直接选择排序算法思想：每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列的最后，直至全部记录排完为止。直接选择排序过程原始数据(49,38,65,97,76,13,27,49)i=113,(38,65,97,76,49,27,49)i=213,27,(65,97,76,49,38,49)i=313,27,38,(97,76,49,65,49)i=413,27,38,49,(76,97,65,49)i=513,27,38,49,49,(97,65,76)i=613,27,38,49,49,65,(97,76)i=713,27,38,49,49,65,76,(97)直接选择排序算法voidSelectSort(SqList&L){ inti,j,k; for(i=1;i<L.n;i++){/*进行n-1趟选择排序*/ k=i; for(j=i+1;j<=L.n;j++)/*选关键字最小的记录*/ if(L.r[j].key<L.r[k].key)k=j;if(k!=i){ /*交换L.r[i]和L.r[k]*/ L.r[0]=L.r[i]; L.r[i]=L.r[k]; L.r[k]=L.r[0]; }}}

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

最大值为3(n-1)。简单选择排序——算法时间性能分析317.2.5归并排序通过“归并”两个或两个以上的有序子序列，逐步增加有序序列的长度，直到所有的记录都进入一个有序序列中为止。32归并排序思路在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列32归并为一个记录的有序序列有序序列L.r[l..n]有序子序列L.r[l..m]有序子序列L.r[m+1..n]归并排序过程3352,23,80,36,68,14[52][23][80]

[36][68][14][23,52][36,80][14,68][23,36,56,80][14,68][14,23,36,52,68,80]一次“归并排序”的算法34voidmerge(SqList&L,SqList&L1,intlow,intmid,inthigh){ inti,j,k; i=low; j=mid+1; k=low; while((i<=mid)&&(j<=high)){ if(L.r[i].key<=L.r[j].key) L1.r[k++]=L.r[i++]; else L1.r[k++]=L.r[j++]; } while(i<=mid)L1.r[k++]=L.r[i++]; while(j<=high) L1.r[k++]=L.r[j++];}一趟“归并排序”的算法voidmergePass(SqList&L,SqList&L1,intlength){ inti,j; i=1; while(i+2*length-1<=L.n){ merge(L,L1,i,i+length-1,i+2*length-1); i=i+2*length; } if(i+length-1<L.n)//最后一个文件长度小于length merge(L,L1,i,i+length-1,L.n); else//子文件个数为奇数 for(j=i;j<=L.n;j++) L1.r[j]=L.r[j];}35归并排序算法voidmergeSort(SqList&L){ intlength=1;SqListL1; L1=L; while(length<L.n){ mergePass(L,L1,length); length=2*length; mergePass(L1,L,length); length=2*length; }}容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlog2n)。即：每一趟归并的时间复杂度为O(n)，总共需进行

log2n

趟。归并排序的特点：是一种稳定性排序方法。辅助空间复杂度：O(n)，时间复杂度：Ο(nlog2n)。归并排序——性能分析7.2.6快速排序首先对无序的记录序列进行“一次划分”，之后分别对划分后的两个子序列“递归”进行快速排序。38无序的记录序列无序记录子序列(1)无序记录子序列(2)枢轴一次划分分别进行快速排序快速排序过程39lowhigh设L.r[low].key=52为枢轴将L.r[high].key和枢轴的关键字进行比较，要求L.r[high].key≥枢轴的关键字将L.r[low].key和枢轴的关键字进行比较，要求L.r[low].key≤

枢轴的关键字high23low80high14low5252lowhighhighhighlow一趟快速排序（一次划分）目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录移至该记录之前，反之，移至该记录之后。一趟排序之后，无序序列L.r[low]...L.r[high]将被分割成两个部分：40L.r[low]...L.r[i-1]和L.r[i+1]…L.r[high]且L.r[k].key≤L.r[i].key≤L.r[j].key(low≤k≤i-1)

枢轴

(i+1≤j≤high)快速排序过程4123,10,20,36,40,13,27,1111,10,20,13,

23,40,27,3610,

11,20,13,23,40,27,3610,11,13,

20,23,40,27,3610,11,13,20,23,36,27,4010,11,13,20,23,27,

36,4010,11,20,13,

23,40,27,3610,11,13,20,23,40,27,36快速排序算法voidqksort(SqList&L,ints,intt){//s为起始位置，t为终止位置intk;if(s<t){k=qkpass(L,s,t);//一次划分qksort(L,s,k-1);qksort(L,k+1,t);}}42快速排序中划分算法intqkpass(SqList&L,ints,intt){ DataTypex; inti,j,m;i=s;j=t;x=L.r[s].key;while(i<j){while((i<j)&&(L.r[j].key>=x))j--; L.r[i]=L.r[j];while((i<j)&&(L.r[i].key<=x))i++;L.r[j]=L.r[i];}L.r[i].key=x;returni;}43堆是满足下列性质的记录序列{r1,r2,…，rn}：或{12,36,27,65,40,34,98,81,73,55,49}例如:是正堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(正堆)(逆堆)1234567891011堆的定义7.2.7堆排序rir2ir2i+1通常将该记录序列看作一棵完全二叉树，则r2i

是ri

的左孩子；r2i+1

是ri

的右孩子。1236276549817355403498是堆14不堆排序——堆的定义正堆的树根是关键字最小的记录。1236276540349849817355496739263440918131598逆堆的树根是关键字最大的记录。堆排序——堆的例子

堆排序是指利用堆的特性对记录序列进行排序的一种排序方法。基本过程：1.根据原始记录序列创建堆；2.将根与堆中的最后一个结点交换；3.将堆中的最后结点从堆中删去；4.将剩余的结点重新调整成堆。堆排序——堆排序的定义1、如何“建初堆”？需要解决的两个问题:2、如何调整“堆”？堆排序——堆的建立所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。堆排序通过不断筛选实现。堆堆筛选堆排序——筛选的定义9881497355641236274012在98和12进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。98128173641298堆排序——1趟排序的过程73496455129836274081在81和12进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。1281比较1273比较645512堆排序——2趟排序的过程736449551