数据结构10排序

第十章排序内容提要本课主题：排序的概念、插入排序，冒泡排序、快速排序，选择排序，堆排序，归并排序，其它排序方法教学目的：掌握排序的根本概念，掌握插入排序、冒泡排序、快速排序，选择排序，堆排序，归并排序算法，了解其它排序方法教学重点：插入排序、冒泡排序、快速排序，选择排序，堆排序，归并排序教学难点：快速排序，堆排序一、排序概述排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。以下图所示给出了两组按年龄排序的结果。注意其中有两个人的年龄相同。排序的稳定性键值相等的记录排序前后相对顺序不变的排序方法是稳定的！键值相等的记录排序前后相对顺序可能更改的排序方法是不稳定的！提问：上图所示两个排序其稳定性怎样？——前者不确定，后者不稳定一般稳定性不重要，但是有些特殊场合，如银行、司法、招生等特别关心先后顺序的场合要注意稳定性问题排序的分类内部排序：待排序记录存放在计算机的内存中进行的排序过程；外部排序：待排序记录数量很大，以致内存一次不能容纳全部记录，在排序过程中需对外存进行访问的排序过程。外部排序的效率主要取决于外存的访问频度。排序方法分类排序方法：构造二叉排序树本身也是一个排序过程交换排序(起泡排序、快速排序)选择排序(简单项选择择排序，堆排序)插入排序(直接插入排序、希尔排序)归并排序基数排序二、交换排序★1、起泡排序(冒泡排序)每一趟都从头部(或尾部)开始依次交换相邻逆序记录，直到在某趟排序过程中没有进行过交换记录的操作为止冒泡排序voidBubbleSort(SqList&L){

for(i=1;i<L.length;++i)//i：趟次，即一趟冒泡后最小元素在结果表中的位序。

//每一趟交换L.r[i～length]中相邻逆序元素

//结果：最小元素到达第i处

for(j=L.length-1;j>=i;--j)//交换L.r[i～length]中相邻逆序元素。

//注意前后两个循环语句的走向相反

if(L.r[j+1].key<L.r[j].key)//这里下标＝位序

L.r[j+1]<--->L.r[j];//注意无else语句}冒泡排序算法2(参见P16，改进方法：一旦某趟没有进行过交换操作那么排序结束，设置change标志标识之)：voidBubbleSort(SqList&L){

for(i=1,change=true;i<L.length&&change==true;++i)

{

//i：趟次，一趟冒泡后最小元素在结果表中的位序

change=false;

for(j=L.length-1;j>=i;--j)//从后向前交换相邻逆序元素

if(L.r[j+1].key<L.r[j].key)//这里下标＝位序

{L.r[j+1]<--->L.r[j];change=true;}//注意无else语句

}}//结束条件是该趟没有进行过交换操作冒泡排序性能分析性能分析：比较操作：O(n2)；移动操作：O(n2)。辅助空间：1。稳定性：稳定提问：对整数序列32154进行从小到大的排序，经过一趟冒泡排序之后的序列怎样？完成排序至少需要多少趟？答：13245，3趟。从左到右时：21345，3趟问题：如何增加交换的跨度以提高性能？快速排序★2、快速排序提问：编写算法将线性表中所有负数排在非负数前，要求时间复杂度、空间复杂度越低越好。比较n次，移动2n次，空间2n比较n次，移动2n次，空间n比较n次，最多移动1.5n次，空间1比较n次，最多移动n+1次，空间1快速排序每一趟排序以某个元素为基准将待排记录分割成独立的两局部，小于基准的记录放在基准的前面，大的放在后面。该基准称之为枢轴。例如以第一个元素为基准，经一趟排序后期望到达的效果如图：下一趟排序，由于比较操作将局限在各局部内进行，不会与整个表中每个元素逐一比较，比较次数会逐趟减半，趟次也大大减少。如图：快速排序提问：1.快速排序稳定吗？为什么？答：不稳定，例如如果元素27是38!2.对整数序列32154、45124736、34323432进行从小到大的排序，求经过一趟快速排序(划分)后的序列？答：12354、32144756、223334343.对恰好有序或逆序的序列进行一趟划分，求元素移动次数。答：恰好有序时2次；恰好无序时3次。4.编写算法将线性表中所有负数排在非负数之前。答：借助划分的思路，或前几页最后一个方法(如图,但不一定好)比较n次，最多移动n+1次，空间1比较n次，最多移动n+1次，空间1快速排序划分算法的整体思路：Partition(L){暂存枢轴：t=L.r[low]while(low<high){ 从右向左找关键字比枢轴小的元素 移动该元素：L.r[low]=L.r[high] 从左向右找关键字比枢轴大的元素 移动该元素：L.r[high]=L.r[low]} 枢轴归位：L.r[low]=t}intPartition(SqList&L,intlow,inthigh)//以顺序表L.r[low～high]的首元素为枢轴,将关键字比它小的记录置于其左侧,大的置于其右侧,并返回枢轴最终位置。该过程称为一趟快速排序或一次划分。参见P274{

L.r[0]=L.r[low];pivot_key=L.r[low].key;//暂存枢轴(首元素)。

//注意low不一定是1，也不要把L.r[0]误看作L.r[low-1]

while(low<high)//从顺序表的两端交替向中间扫描，直到low==high

{

while(low<high&&L.r[high].key>=pivot_key)--high;

//高端比枢轴大的记录位置保持不变

L.r[low]=L.r[high];

//高端比枢轴小的记录移动到低端。

while(low<high&&L.r[low].key<=pivot_key)++low;

//高端比枢轴大的记录位置保持不变

L.r[high]=L.r[low];

//高端比枢轴小的记录移动到低端

}

L.r[low]=L.r[0];//low==high时结束循环，该处即枢轴最终位置

returnlow;}或为if(low<high)L.r[low++]=L.r[high];但不能省略if判断，否那么上一句while循环最后是执行—high时，返回的low值有问题注意不能省略两处比较中的等号，否那么死循环快速排序voidQSort(SqList&L,intlow,inthigh)//对顺序表L.r[low～high]作快速排序{

if(low<high)//表长大于1

{

pivot_location=Partition(L,low,high);

//以枢轴为基准，将顺序表一分为二，返回枢轴位置

QSort(L,low,pivot_location-1);

//对枢轴低端子表递归排序

QSort(L,pivot_location+1,high);//对枢轴高端子表递归排序

}}例子程序参见：sort.cpp快速排序性能分析：平均时间复杂度：O(nlogn)，最坏时，如序列恰好有序或恰好逆序时为：O(n2)。辅助空间：O(logn)，最坏时为O(n)(实现递归算法需要栈空间，最坏时会递归n层)。但注意存储记录的辅助空间只需要1个稳定性：不稳定。三、选择排序★1.简单项选择择排序每一趟从第i到第n个元素中选取关键字最小的记录将其放到第i个位置(如最小记录与第i个记录交换)简单项选择择排序算法1：voidSelect_Sort(SqList&L){

for(i=1;i<L.length;i++)//i：趟次，即找到的最小元素的目标位置。

{

//每趟从L.r[i～length]中找出最小的元素，与第i个元素交换

min=i;//首先假设子表中首元素最小

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

//注意前后两个循环走向相同

if(L.r[j].key<L.r[min].key)min=j;

if(min!=i)L.r[min]<--->L.r[i];//将该记录与第i个记录交换

}}简单项选择择排序算法2(P277)：

voidSelect_Sort(SqList&L)

{

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

{

j=SelectMinKey(L,i);//在L.r[i..length]中查找key最小的记录

if(i!=j)L.r[i]<--->L.r[j];//将该记录与第i个记录交换

}

}例子程序参见：sort.cpp简单项选择择排序提问：1.简单项选择择排序稳定吗？答：上述算法不稳定(如首元素为38时)。但找到最小元素后假设将其插入到目标位置，那么算法是稳定的！2.对整数序列32154进行从小到大的排序，经过一趟简单项选择择排序之后的序列怎样？答：12354，如果采用顺序移动策略，那么为13254简单项选择择排序与冒泡排序的区别：交换数量减少、趟次增加、不稳定。问题：如何提高选择的速度以提高性能？树形选择排序2.树形选择排序引言：如何减少简单项选择择排序的比较次数：第二趟找最小的元素时利用前一趟的比较结果。例如：49，38，65，97，76，13，27，49*，第一趟中存在的比较：49－38，38－65，38－97，38－76，38－13，13－27，13－49*。决出冠军13之后，选亚军只需要比较38，27，49*(因49，65，97，76已与38比较过)。如果把两两比较作为一种数据间的关系，该操作可以用以下图形象表示：树形选择排序树形选择排序(锦标赛排序)：首先对n个记录的关键字进行两两比较，然后在其中一半较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止。利用树形结构很容易理解和实现。注意该方法与通过构造二叉排序树来排序不同(二叉排序树的非终端结点存储有真正的记录)堆排序★3.堆排序引言：树形选择排序需要构建一个完全二叉树(不是满二叉树，为什么？)，非终端结点并不存储元素，辅助空间多。改进方法：让每个结点都存储元素，最紧凑的方法是使用完全二叉树的顺序存储结构，为了让树根关键字值最小，需要改进策略。答：是，小顶堆堆排序堆：n个元素的序列{k1,k2,...,kn}当且仅当满足以下关系时，称之为堆(小顶堆)：ki<=k2i且ki<=k2i+1(i=1,2,...,n/2)。(或者说满足ki>=k[i/2],i=2,3,...,n)理解：它对应的二叉树中各结点都小于两个孩子结点(故不是二叉排序树)。提问：序列123456是堆吗？堆排序利用堆可以搜寻最小元素，进而可用来排序。方法是输出堆顶元素(如把堆顶元素与最末元素交换)，然后把剩余元素调整为堆，再输出堆顶元素、再调整…利用堆排序要解决两个问题：如何由一个无序序列建成一个堆——初建堆输出堆顶元素后，如何调整剩余元素成为一个新的堆——堆调整或筛选堆排序问题2的解决方法：注：排序思路——按图示过程不断对小顶堆进行输出堆调整，各趟堆调整全部结束以后，整个序列将变成一个从大到小的有序序列。堆排序问题1的解决方法(基于堆调整完成初建堆)：堆排序算法(注:要使排序结果从小到大，要建立大顶堆)：typedefSqListHeapType;voidHeapAdjust(HeapType&H,ints,intm){

//记录H.[s～m]中除首元素外均满足堆定义，该算法将把该记录调整为堆

rc=H.r[s];

//暂存首元素

for(j=2*s;j<=m;j*=2)//从“孩子〞结点开始进行调整

{

//j号元素是s号元素的孩子

if(j<m&&H.r[j].key<H.r[j+1].key)++j;//比较哪个孩子更大

if(rc.key>=H.r[j].key)break;//比较“堆〞顶元素与较大的孩子

H.r[s]=H.r[j];s=j;//较大的孩子置顶，再调整孩子堆

}

//调整孩子堆，把首元素与孩子的孩子进行比较，此处不是递归调用

H.r[s]=rc;//把首元素放到目标位置，堆调整结束}堆排序voidHeapSort(HeapType&H){

for(i=H.length/2;i>0;i--)

HeapAdjust(H,i,H.length);//初建堆

for(i=H.length;i>1;i--)

{

H.r[1]<--->H.r[i];

//交换堆顶元素与尾元素

HeapAdjust(H,1,i-1);//重新调整除尾元素外的剩余元素为堆

}}堆排序只需1个记录大小的辅助空间。堆排序提问：1.整数序列12345组成的小顶堆，其首元素输出后，一趟堆调整的结果如何？答：243512.整数序列32154初建堆的结果如何？答：小顶堆：12354；大顶堆：54123堆排序性能分析：

时间复杂度：O(nlogn)

空间复杂度：O(1)

稳定性：不稳定四、插入排序★1、直接插入排序每一趟将一个新记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表直接插入排序算法1：voidInsertSort(SqList&L){

for(i=2;i<=L.length;++i)//i：待插元素的位序。每一趟把元素L.r[i]

//插入到有序子表L.r[i-1～1]中。i从2开始

for(j=i-1;j>=1;--j)//j：可能需要移动的元素的位序。注意前、后两循环语句走向相反

if(L.r[j+1].key<L.r[j].key)L.r[j+1]<--->L.r[j];

elsebreak;}直接插入排序算法2(P265，插入元素需要移动元素，但可以顺次移动元素；使用哨兵)：voidInsertSort(SqList&L){

for(i=2;i<=L.length;++i)//每一趟把元素L.r[i]插入到有序子表中。

if(L.r[i].key<L.r[i-1].key)//此时才需插入L.r[i]到有序子表中

{

L.r[0]=L.r[i];

//复制哨兵，暂存元素L.r[i]

L.r[i]=L.r[i-1];

//把大于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[i]的记录L.r[j]后移。

L.r[j+1]=L.r[0];

//把元素L.r[i]插入到正确位置

}}例子程序参见：sort.cpp直接插入排序提问：对整数序列32154进行从小到大的排序，经过一趟直接插入排序之后的序列怎样？答：23154性能分析：

比较操作：顺序查找O(n2)；移动操作：顺序移动O(n2)，时间复杂度：O(n2)。

辅助空间：1。

稳定性：稳定。直接插入排序改进方法：

折半插入排序——折半查找，顺序插入；

2-路插入排序——折半查找，2路插入(以首元素为基准，将剩余元素分成两个局部排序，可减少插入操作)；

表插入排序——基于链表顺序查找，修改指针代替移动记录希尔排序2.希尔排序(缩小增量排序)直接插入排序在n很小和序列根本有序时都很高效。故可以把记录大跨度方式分组，组内排序之后，整个序列便根本有序，然后缩小跨度继续分组、排序。希尔排序希尔排序需要选择恰当的增量序列，至少应当令其互质，且最后一个增量必须是1。希尔排序不稳定。希尔排序的规律比较复杂，时间复杂度可以近似认为是n1.3，其高效的原因源于元素的跳跃式移动。算法参见课本P272。希尔排序提问：对整数序列32154进行从小到大的排序，经过一趟希尔排序(增量为3)之后的序列怎样？答：32154(原封不动)。增量为2时结果为：12354；增量为1时结果为：12345(虽只1趟，但蜕化为插入排序)★五、归并排序将两个或两个以上的有序表组合成一个新的有序表的方法叫归并。假设初始序列含有n个记录，那么可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复。由于归并排序需要的辅助空间较多，内部排序很少使用归并排序方法。归并排序归并排序的实现：注意是先等分，再等分，直到表长为1以后才开始归并，且是对相邻子表进行归并。voidMerge(ElemTypeSR[],ElemType&TR[],inti,intm,intn){

//归并有序表SR[i～m]和SR[m+1～n]为TR[i～n]。

//思路类似于P26程序，不同之处是该算法是归并一个表的两个局部，而不是归并两个表}归并排序voidMSort(ElemTypeSR[],ElemType&TR1[],ints,intt){

if(s==t)TR1[s]=SR[s];//递归调用终止条件

else

{

mid=(s+t)/2;

//将SR[s～t]平分为SR[s～m]和SR[m+1～t]两局部

MSort(SR,TR2,s,mid);

//归并排序SR[s～m]为TR2[s～m]

MSort(SR,TR2,mid+1,t);

//归并排序SR[m+