数据结构授课教师教学案内部排序Word格式文档下载.docx
《数据结构授课教师教学案内部排序Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构授课教师教学案内部排序Word格式文档下载.docx（21页珍藏版）》请在冰点文库上搜索。
作业布置
习题10
参考书
1.数据结构题集（C语言版）,严蔚敏，清华大学出版社，2002。
3.数据结构、算法与应用－C++语言描述，（美）SartajSahni著，汪诗林等译，机械工业出版社，2002。
课型
理论课
学
时
分
配
复习
分钟
主要教具
投影、黑板
讲授
教学方法
讲解、提问、示例
指导
教学手段
板书、课件
总结
备注
共8学时，其中2学时为习题课
注：
课型一栏填写理论课、实验课、习题课等
授课内容
第10章排序
10.1概述
为了便于查找，通常希望计算机中的数据表是按关键码有序的。
如有序表的折半查找，查找效率较高。
还有，二叉排序树、B-树和B+树的构造过程就是一个排序过程。
排序（sorting）是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按关键码有序的序列。
1.排序的定义
（1）排序的定义：
设{R1,R2,…,Rn}是由n个记录组成的文件，{K1,K2,…,Kn}是排序码集合，所谓排序是将记录按排序码递增（或递减）的排列。
排序码可以是主关键码，也可以是次关键码。
（2）稳定性
假设Ki=Kj（1≤i,j≤n,i≠j），且在排序前的序列中Ri领先于Rj（即i<
j），若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的，否则是不稳定的。
（3）排序的分类：
待排序的记录在排序过程中全部存放在内存的称为内排序，如果排序过程中需要使用外存的称为外排序。
按排序原则，排序分为：
1插入排序；
2选择排序；
3交换排序
4分配排序
5归并排序
6外部排序
按排序所需的工作量，排序分为：
1简单排序方法，其时间复杂度为O（n2）；
2先进的排序方法，其时间复杂度为O（nlogn）；
3基数排序，其时间复杂度为O（d·
n）；
（4）排序中的基本操作：
1比较关键码大小
2移动记录
（5）对于待排序的记录序列，有三种常见的存储表示方法。
1向量结构，即将待排序的记录存放在一组地址连续的存储单元中。
2链表结构。
3记录向量与地址向量结合，即将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。
为简单起见，数据的存储结构采取向量的存储结构：
#definen20//记录数
typedefintkeytype;
typedefstruct{
keytypekey;
datatypeother;
}rectype;
rectyper[n+1];
（6）排序算法的评价：
1算法的执行时间
2算法执行时所需的附加空间
10.2插入排序
基本原理：
每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。
10.2.1直接插入排序
1直接插入排序的基本思想
先假定第1个记录为有序序列，然后从第2条记录开始，依次将记录插入到前面已经有序的序列中，直至全部记录有序。
一般情况下，第i趟直接插入排序：
将r[i]插入到已经有序的序列r[1..i-1]中，使其变成有序序列r[1..i]。
整个排序进行n-1趟插入。
2示例：
初始：
[49]38659776132749
3算法：
voidInsertSort（rectypeR[],intn）{
inti,j;
for（i=2;
i<
n;
i++）{
R[0]＝R[i];
for（j＝i-1;
R[0].key<
R[j].key;
j--）
R[j+1]＝R[j];
R[j+1]＝R[0]
}
}
4算法分析：
空间效率：
只需要一个记录的辅助空间。
时间效率：
比较记录的次数为：
最小：
n-1次；
最大:
（n+2）（n-1）/2次
移动记录的次数：
2（n-1）最大:
（n+4）（n-1）/2
平均情况：
O（n2）
10.2.2折半插入排序
1、折半插入排序：
将直接插入排序的查找过程改用折半查找。
由此实现的排序称为二分法插入排序。
10.2.3希尔排序（Shell’sSort）
1、希尔排序：
shell排序又称缩小增量排序（DiminishingIncrementSort）。
先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序“时，再对全体记录进行一次直接插入排序，就可以完成整个的排序工作。
利用下面两点：
当n很小时，直接插入排序的效率较高；
当待排记录序列基本有序时，直接插入排序的效率也较高。
shell排序对直接插入排序算法进行改进。
例：
原始序列4938659713762749’
voidshellSort（rectyper[],intn,intd[],intk）{
for（l=0;
l<
k;
l++）{
dk＝d[l];
for（i=dk+1;
=n;
r[0]＝r[i];
for（j=i-dk;
（j>
0&
&
R[j].key>
r[0].key）;
j-=dk）
r[j+dk]＝r[j];
R[j+dk]＝r[0];
2、算法分析：
Shell排序的平均比较次数和平均移动次数都为O（n1.3）左右
Shell排序算法中增加了一个辅助空间。
Shell排序是不稳定的。
10.3交换排序
交换排序基本思想：
两两比较待排序记录的排序码，交换不满足排序要求的偶对，直到全部有序。
10.3.1冒泡排序（BubbleSort）
1、基本思想：
设待排序记录顺序存放在R1,R2,R3,…,Rn中:
依次比较（R1,R2），（R2,R3）,…,（Rn-1,Rn）,不满足顺序则交换，结果，最大者在Rn中。
这叫一次起泡。
此后，再对存放在R1,R2,R3,…,Rn-1中n-1个记录作同样处理,结果，最大者在Rn-1中。
…。
n-1次起泡能完成排序。
设置标志noswap表示本次起泡是否有交换，若无交换，表示排序完成。
2、示例：
3、算法：
voidbubbleSort（rectypeR[],intn）{
i=1;
flag=1;
for（i=1;
n&
flag;
i++）{
flag＝0;
for（j=1;
j<
=n-i;
j++）
if（R[j].key>
R[j+1].key）{
temp＝R[j+1];
R[j+1]=R[j];
R[j]＝temp;
flag＝1;
4、算法分析：
起泡排序的最坏时间复杂度为O（n2），平均时间复杂度为O（n2）。
起泡排序算法中增加一个辅助空间temp，辅助空间为S（n）=O
（1）。
起泡排序是稳定的。
10.3.2快速排序（QuickSort）
快速排序的基本思想是：
从待排序记录序列中选取一个记录（通常选取第一个记录）作为“枢轴”，通过一趟排序（一次划分）将待排记录分割成独立的两部分，其中一部分记录的关键字比枢轴小，另一部分记录的关键字比枢轴大。
然后则可分别对这两部分记录继续进行划分，以达到整个序列有序。
一趟快速排序（一次划分）的具体做法是：
附设两个指针low和high,它们的初值分别是一个序列的第一个和最后一个记录的位置，设枢轴记录的关键字为pivotKey，在首先从high所指位置起向前搜索直到第一个关键字小于pivotKey的记录和枢轴记录交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotKey的记录和枢轴记录互相交换，重复交替这两步直到low=high为止。
设记录的关键码序列为：
4938659776132749
对其进行快速排序。
intPartition（rectypeR[],intn,intlow,inthigh）
{
pivotkey=R[low].key;
while（low<
high）{
while（（low<
high）&
（R[high].key>
=pivotkey））
--high;
r[low]=r[high];
while（（low<
（R[low].key<
++low;
r[high]=r[low];
r[low]=pivotkey;
returnlow;
voidQSort（rectypeR[],intn,intlow,inthigh）{
if（low<
high）{
pivotloc=Partition（R,n,low,high）;
QSort（R,low,pivotloc-1）;
QSort（R,pivotloc+1,high）;
voidQuickSort（rectypeR[],intn）{
QSort（R,n,1,n）;
最坏情况下，即当初始序列已经有序时，快速排序退化为起泡排序，为O（n2）。
最好时间复杂度为O（nlog2n）。
平均时间复杂度是T（n）=O（nlog2n）。
算法需要一个栈空间实现递归。
栈的大小取决于递归调用的深度，最多不超过n，理想情况下不超过log2n。
所以快速排序的辅助空间最坏为S（n）=O（n），最好为S（n）=O（log2n）。
快速排序是不稳定的。
10.4选择排序
选择排序（SelectionSort）的基本思想是：
每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
10.4.1简单选择排序（SimpleSelectionSort）
第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。
共需进行i-1趟比较，直到所有记录排序完成为止。
voidSelectSort（rectypeR[],intn）{
=n-1;
k=i;
for（j=i+1;
if（R[j].key<
R[k].key）k=j;
if（k!
=i）{
temp=R[i];
R[i]=R[k];
R[k]=temp;
直接选择排序的比较次数与文件初始状态无关。
直接选择排序的时间复杂度：
移动：
最好：
0最坏：
3（n-1）
比较：
n（n-1）/2
总的时间复杂度：
稳定性：
不稳定
10.4.2树形选择排序（TreeSelectionSort）
1基本思想：
简单选择排序的主要操作是比较，要提高它的速度必须减少比较的次数。
而实际上如果能利用以前的比较结果则可以提高排序速度。
树形选择排序（TreeSelectionSort），又称锦标赛排序（Tournamentsort）,其方法是：
首先对n个记录的关键字进行两两比较，然后在⎡n/2⎤个较小者之间再进行两两比较，如此重复直到选出最小关键字的记录为止。
然后对剩下的记录作同样的操作，选出具有次小关键字的记录。
这个过程可以用一个完全二叉树来表示。
3算法分析：
在树型选择排序中，含有n个叶子节点的完全二叉树的深度为┌log2n┐+1，则在树型选择排序中，每选择一个小关键字需要进行┌log2n┐次比较，因此其时间复杂度为O（nlog2n）。
移动记录次数不超过比较次数，故总的算法时间复杂度为O（nlog2n）。
缺点是使用了较多的辅助空间（n-1），并且和“最大值”进行了多余的比较。
10.4.3堆排序（HeapSort）
1堆的定义：
堆排序是对树型选择排序的进一步改进。
采用堆排序时，只需要一个记录大小的辅助空间。
1964年Willioms提出了堆排序。
堆的定义：
n个元素的序列{k1,k2,…,kn}当且仅当满足如下关系时，称之为堆。
ki≤k2iki≥k2i
ki≤k2i+1ki≥k2i+1
（i=1,2,…,⎣n/2⎦）
若将和此序列对应的一维数组看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不小于（或不大于）其左右孩子结点的值。
2堆排序的基本思想：
若序列{k1,k2,…,kn}是堆，则堆顶元素必为序列中n个元素的最大值（或最小值）。
如果在输出堆顶的最大值后，使得剩余n-1个元素的序列重又建成一个堆，则得到次大值。
反复执行便能得到所有记录的有序序列，这个过程称为堆排序。
现在剩下两个问题：
（1）如何由一个无序序列建成一个堆；
（2）如何在输出堆顶元素后，调整剩余元素为一个新的堆。
问题1:
当堆顶元素改变时，如何重建堆?
“筛选”法调整成堆。
问题2:
如何由一个任意序列建初堆？
一个任意序列看成是对应的完全二叉树，由于叶结点可以视为单元素的堆，因而可以反复利用“筛选”法，自底向上逐层把所有子树调整为堆，直到将整个完全二叉树调整为堆。
对无序序列{49,38,65,97,76,13,27,49}建堆示例：
问题3:
如何利用堆进行排序？
进行堆排序的步骤：
①将待排序记录按照堆的定义建初堆，并输出堆顶元素；
②调整剩余的记录序列，利用筛选法将前n-i个元素重新筛选建成为一个新堆，再输出堆顶元素；
③重复执行步骤②n-1次进行筛选,新筛选成的堆会越来越小，而新堆后面的有序关键字会越来越多，最后使待排序记录序列成为一个有序的序列，这个过程称之为堆排序。
初始序列为
26，5，77，1，61，11，59，15，48，19
voidSift（rectypeR[],ints;
intm）{//筛选算法
temp=R[s];
for（j=2*s;
=m;
j*=2）{
if（（j<
m）&
（R[j].key<
R[j+1].key））
j++;
if（temp.key>
=R[j].key）break;
R[s]=R[j];
s=j;
R[s]=temp;
//堆排序算法
voidHeapSort（rectypeR[],intn）{
for（i=n/2;
i>
=1;
i--）//初始建堆
Sift（R,i,n）;
for（i=n;
1;
i--）{
temp=R[1];
R[1]=R[i];
R[i]=temp;
Sift（R,1,i-1）;
初始建堆比较次数为：
O（n）
排序中比较次数为：
<
O（n*log2n）。
移动次数小于比较次数。
在最坏的情况下，时间复杂度也是O（nlogn）。
且仅需一个记录大小的辅助空间。
堆排序适用于n值较大的情况。
堆排序是不稳定的排序方法。
10.5归并排序
归并的含义是将两个或两个以上的有序表合并成一个有序表。
利用归并的思想就可以实现排序。
假设初始的序列含有n个记录，可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到⎡n/2⎤个长度为2或1的有序子序列；
再两两归并，如此重复直到得到一个长度为n的有序序列为止。
这种排序方法称为二路归并排序。
voidMerge（rectypeR[],rectypeR1[],intlow,intmid,inthigh）{
i=low;
j=mid+1;
k=low;
while（（i<
=mid）&
（j<
=high））
if（R[i].key<
=R[j].key）R1[k++]=R[i++];
elseR1[k++]=R[j++];
while（j<
=mid）R1[k++]=R[i++];
=high）R1[k++]=R[j++];
voidMSort（rectypeR[],rectypeR1[],ints,intt）{
if（s==t）r1[s]=r[s];
else{
m=（s+t）/2;
MSort（R,R2,s,m）;
MSort（R,R2,m+1,t）;
Merge（r2,r1,s,m,t）;
voidMergeSort（rectypeR[],intn）{
MSort（r,r,1,n）;
时间复杂度:
O（nlog2n）
空间复杂度:
和待排记录等量的空间.
二路归并算法是稳定的.
一般情况下很少用于内部排序.
10.6分配排序
分配类排序则利用分配和收集两种基本操作，基数类排序就是典型的分配类排序。
分配排序的思想是把排序码分解成若干部分，然后通过对各个部分排序码的分别排序，最终达到整个排序码的排序。
10.6.1概述
一般情况下，假设文件F有n个记录
F=（R0，R1，…Rn-1）
且每个记录Ri的排序码中含有d个部分（ki0,ki1,…,kid-1），则文件F对排序码（k0,k1,…,kd-1）有序是指∶文件中任意两个记录Ri和Rj（0≤i≤j≤n-1）满足词典次序有序关系
（ki0,ki1,…,kid-1）<
（kj0,kj1,…,kjd-1）
其中k0称为最高位排序码，kd-1称为最低位排序码。
实现分配排序，有两种方法∶第一种是先对最高位排序码k0排序，称为最高位优先法（MostSignificantDigitfirst）。
第二种是先对最低位排序码kd-1排序，称为最低位优先法（LeastSignificantDigitfirst）。
例如：
我们可以将一副扑克牌的排序过程看成由花色和面值两个关键字进行排序的问题。
若规定花色和面值的顺序如下：
花色：
梅花<
方块<
红桃<
黑桃
面值：
A<
2<
3<
…<
10<
J<
Q<
K
并进一步规定花色的优先级高于面值，则一副扑克牌从小到大的顺序为：
梅花A，梅花2，…，梅花K；
方块A，方块2，…，方块K；
红桃A，红桃2，…，红桃K；
黑桃A，黑桃2，…，黑桃K。
最高位优先：
先按花色分成有序的四类，然后再按面值对每一类从小到大排序。
最低位优先：
先按面值从小到大把牌摆成13叠（每叠4张牌），然后将每叠牌按面值的次序收集到一起，再对这些牌按花色摆成4叠，每叠有13张牌，最后把这4叠牌按花色的次序收集到一起，于是就得到了有序序列。
低位优先法比高位优先法简单，高位优先排序必须将文件逐层分割成若干子文件，然后各子文件独立排序；
低位优先排序不必分成子堆，对每个排序码都是整个文件参加排序，且可通过若干次“分配”和“收集”实现排序。
但对Ki（0<
=i<
=d-2）进行排序时，只能用稳定的排序方法。
下面将介绍的基数排序就是用排序码低位优先法的思想对排序码进行分解后排序的一种方法。
10.6.2链式基数排序
采用基数排序首先把每个排序码看成是一个d元组∶
Ki=（Ki0,Ki1,…,Kid-1）
其中每个Ki都是集合{C0，C1，…，Cr-1}（C0<
C1<
Cr-1）中的值，即C0≤Kij≤Cr-1（0≤i≤n-1,0≤j≤d-1），其中r称为基数。
排序时先按Kid-1从小到大将记录分配到r个堆中，然后依次收集，再按Kid-2分配到r个堆中，如此反复，直到对Ki0分配、收集，得到的便是排好序的序列。
基数排序算法中，时间耗费主要在修改指针上。
一趟排序的时间为O（r+n）。
总共要进行d趟排序，基数排序的时间复杂度是T（n）=O（d*（r+n））。
当n较大、d较小，特别是记录的信息量较大时，基数排序非常有效。
基数排序中，增加了一个queue数组，故辅助空间为S（n）=O（r）。
基数排序是稳定的。
10.7各种排序方法的比较讨论
一、选取排序方法时需要考虑的因素有：
●待排序的记录数目
●记录本身信息量的大小
●关键字的结构及其分布情况
●对排序稳定性的要求
●语言工具的条件、辅助空间的大小
二、各种排序方法的综合比较
结论：
（1）平均时间性能：
以快速排序法最佳，但最坏情况下不如堆排序和归并排序；
在n较大时，归并排序比堆排序快，但所需辅助空间最多。
（2）简单排序以直接插入排序最简单，当下列中记录“基本有序“或n值较小时，是最佳的排序方法。
因此常和其他排序方法结合使用。
（3）基数排序最适用于n值很大而关键字较小的序列。
若关键字也很大，而序列中大多数记录的”最高位关键字”均不同，则也可以先按“最高位关键字”不同将序列分成若干个子序列，而后用直接插入排序。
（4）从稳定性来看，基数排序是稳定的排序方法，大部分时间复杂度为O（n2）的简单排序法都是稳定的。
然而，快速排序、堆排序和希尔排序等时间性能较好的排序都是不稳定的。
一般来说，排序过程中的比较是在相邻的两个记录关键字之间进行的排序方法是稳定的。
大多数情况下排序是按记录的主关键字进行的，则所有的排序方法是否稳定无关紧要。
当排序是按记录的次关键字进行时，则应根据问题所需慎重选择。
习题课内容
排序的概念、操作和算法。
要求
1.习题课主要对相关章节布置的习题给出正确或参考答案，对学生作业中容易犯的错误予以纠正。
2.对每章习题中的重点及难点问题进行讨论，并解答学生有关的疑问。
升级会员 