第3章排序1(第6次课)

1

1.双向链表五、其它形式的链表typedefstructDuLNode{ElemTypedata;

//数据域

structDuLNode*prior;

//指向前驱的指针域

structDuLNode*next;

//

指向后继的指针域}

DuLNode,*DuLinkList;2

最后一个结点的指针域的指针又指回第一个结点的链表a1a2…...an2.循环链表

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。3

在循环链表中，头指针也可以改变到指向尾结点，这样用一个头指针就能够控制首位两端，可为有些操作带来便利。a1a2…...an4双向循环链表空表非空表a1a2…...an5双向链表的操作特点：“查询”和单链表相同。“插入”和“删除”时需要同时修改两个方向上的指针。

由于前驱指针的设置，如需要前驱的位置信息时，可直接使用，避免了遍历操作的时间消耗。6ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入7ai-1删除aiai+1p->next=p->next->next;p->next->prior=p;pai-18第3章排序排序本身涉及的数据结构类型比较单纯，所用的存储结构为顺序表。把排序的内容安排在第

2

章的线性表之后，可巩固第

2

章所学的知识，也有利算法分析能力的提高。其中有些排序的内容需要树的知识做基础，这些内容被安排在第

6

章来继续学习。例如，堆排序的实现放到“二叉树的应用”一节；归并排序的跟读需要借助“二叉树遍历”的知识做铺垫等。讲授本章课程大约需6课时。93.1排序的基本概念3.2简单排序方法3.3先进排序方法3.4基数排序3.5各种排序方法的综合比较103.1排序的基本概念一、排序的定义二、内部排序和外部排序三、内部排序方法的分类四、内部排序的数据类型定义11一、排序的定义排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,9712一般情况下，假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：

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

{Rp1,Rp2,

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

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

本章只讨论内部排序。

14三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区15理解一趟选择排序voidSelectPass(SqList&L,inti){RcdTypew; j=i; for(k=i+1;k<=L.length;k++)

if(L.r[k].key<L.r[j].key)j=k; if(i!=j){

w=L.r[j];L.r[j]=L.r[i];L.r[i]=w;}//SelectPass16理解选择排序全过程voidSelectSort(SqList&L,inti){RcdTypew;

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

if(L.r[k].key<L.r[j].key)j=k; if(i!=j){

w=L.r[j];L.r[j]=L.r[i];L.r[i]=w;

}//for}//SelectSort17基于不同的“扩大”

有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法各类排序的主要操作介绍：181.插入类型的排序

将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。因寻找插入位置的方法不同，派生出多种形态的插入排序。192.交换类型的排序

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

从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。除简单选择排序外，堆排序也属于选择类型的排序。214.归并类型的排序

通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。5.其它类型的排序方法22#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置

intlength;//顺序表长度}SqList;//顺序表类型注意：实现时需要定义InfoType如

typedefintInfoType;四、内部排序的数据类型定义233.2简单排序方法一、插入排序二、起泡排序24有序序列R[1..i-1]R[i]无序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]无序序列R[i+1..n]插入排序25实现“一趟插入排序”可分三步进行：3．将R[i]插入(复制)到R[j+1]的位置上。2．将R[j+1..i-1]中的所有记录均后移一个位置；1．在R[1..i-1]中查找R[i]的插入位置，R[1..j].keyR[i].key<R[j+1..i-1].key；26插入排序利用“顺序查找”实现“在R[1..i-1]中查找R[i]的插入位置”算法的实现要点：27从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插入位置28对于在查找过程中找到的那些关键字不小于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上述循环结束后可以直接进行“插入”插入位置29令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];

}30void

InsertionSort(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];//复制为监视哨for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置31内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；32对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：0“移动”的次数：“移动”的次数：33二、起泡排序在实现有序性的过程中，使用了交换的操作34

假设在排序过程中，记录序列R[1..n]的状态为：第i趟起泡排序无序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列R[n-i+1..n]比较相邻记录，将关键字最大的记录交换到n-i+1的位置上起泡排序35void

BubbleSort(ElemR[],intn)

{

while(i>1){

}

//while}//BubbleSorti=n;i=lastExchangeIndex;//本趟进行过交换的

//最后一个记录的位置

if

(R[j+1].key<R[j].key)

{

Swap(R[j],R[j+1]);

lastExchangeIndex=j;//记下进行交换的记录位置

}

//iffor(j=1;j<i;j++)lastExchangeIndex=1;36注意:2.一般情况下，每经过一趟“起泡”，“i减一”，但并不是每趟都如此。例如:2553157989i=7i=6for(j=1;j<i;j++)if

(R[j+1].key<R[j].key)…13i=21.起泡排序的结束条件为，

最后一趟没有进行“交换记录”。37时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡“比较”的次数：0“移动”的次数：“移动”的次数：n-1383.3先进排序方法一、快速排序二、归并排序三、堆排序39一、快速排序在实现有序性的过程中，使用了交换的操作一趟快速排序快速排序快速排序的时间考量40一趟快速排序（一次划分）

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

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

枢轴

(i+1≤k≤t)41stlowhigh设R[s]=52为枢轴

将R[high].key和枢轴的关键字进行比较,要求R[high].key≥

枢轴的关键字

将R[low].key和枢轴的关键字进行比较,要求R[low].key≤

枢轴的关键字high23low80high14low52例如R[0]52lowhighhighhighlow42日后如果不理解一趟快速排序，请再次观看该动画！43可见，经过“一次划分”，将关键字序列

52,49,80,36,14,58,61,97,23,75调整为:23,49,14,36,(52)58,61,97,80,75在调整过程中，设立了两个指针：low和high，它们的初值分别为：s和t，之后逐渐减小high，增加low，并保证

R[high].key≥52，和R[low].key≤52,否则进行记录的“交换”。44intPartition(RedTypeR[],int

low,int

high){}//Partition

R[0]=R[low];

pivotkey=R[low].key;

//枢轴while(low<high){

}while(low<high&&

R[high].key>=pivotkey)--high;

//从右向左搜索，循环结束说明找到小的R[low]=R[high];//R[low]刚才已送走while

(low<high

&&

R[low].key<=pivotkey)

++low;

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

//枢轴记录移到正确位置return

low;//返回枢轴位置“一次划分”的算法45快速排序首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序46void

QSort(RedType&R[],ints,intt)

{

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