数据结构授课教案-第9章内部排序

山东轻工业学院

教师授课教案

课程名称：数据结构（计科）

课程代码：0301306

学分：4.5

课程类别：必修

开课单位：信息科学与技术学院

授课班级:

授课教师：杨春花

山东轻工业学院教务处制

年

第

月

星期

节

日

年

第

星期

月

节

日

授课时间

第

星期

年

日

月

节

第九章内部排序

第一节概述

排序的定义、稳定性、、分类和排序表的存储结构表示。

第二节插入排序

直接插入排序的思想、算法和分析；希尔排序的思想、算法和分析。

授第三节交换排序

课冒泡排序的思想、算法和分析；快速排序的思想、算法和分析。内

第国节选择排序

容简单选择排序的思想、算法和分析；树形选择排序的思想；堆的定义、筛选法

概建堆的过程、堆排序的算法和分析。

要第五节归并排序

归并排序的思想、算法和分析。

第六节基数排序

多关键字排序和链式基数排序。

第七节各种内部排序方法的比较讨论

各种内部排序方法的比较，内部排序的时间复杂度的下界。

盲目的：掌握内部排序的基本方法

的基本要求：理解二路归并排序、堆排序、基数排序的思想和算法，理解各种排序方

要法的特点；掌握排序的基本概念，掌握直接插入排序、希尔排序、简单选择排序、

求冒泡排序、快速排序的思想和算法。

重希尔排序、冒泡排序、堆排序、快速排序、二路归并排序和基数排序。

点

雁■唯排序、快速排序、二路归并排序和基数排序。

点

作

业

领

习

布10

置

参1.数据结构题集（C语言版），严蔚敏，清华大学出版社，2002。

考3.数据结构、算法与应用一C++语言描述，（美）SartajSahni著，汪诗林等译，机书

械二业出版社,2002.

课型理论课学复习分钟

时

主要教具投影、黑板分讲授分钟

配

教学方法讲解、提问、不例指导分钟

教学手段板书、课件总结分钟

共8学时，其中2学时为习题课

备注

注：课型一栏填写理论课、实验课、习题课等

授课内容备注

第10章排序

10.1概述

为了便于查找，通常希翼计算机中的数据表是按关键码有序的。

如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和B+树

的构造过程就是一个排序过程。

排序(sorting)计算机程序设计中的一种重要操作，其功能是对一个数据元

素集合或者序列重新罗列成一个按关键码有序的序列。

1.排序的定义

(1)排序的定义：

设｛Ri，0,卜是由n个记录组成的文件，｛K「F，,卜｝是排序码集合，

所谓排印是“将记录按排序码递增(或者递减)的罗翁

排序码可以是主关键码，也可以是次关键码。

(2)稳定性

假设K「K」(105丽)，且在排序前的序列中5率先于％(即i<j),若在排序后

的序列‘中Rj仍率先于R「则称所用的排序务法是稳,定的，否则是不稳

定的。

(3)排序的分类：

待排序的记录在排序过程中全部存放在内存的称为内排序，如果排序过

程中需要使用外存的称为外排序。

按排序原则，排序分为：

①插入排序；

②选择排序；

③交换排序

④分配排序

⑤归并排序

⑥外部排序

按排序所需的工作量，排序分为：

①简单排序方法，其时间复杂度为O(n2)；

②先进的排序方法，其时间复杂度为O(nlogn)；

③基数排序，其时间复杂度为O(dn.)；

(4)排序中的基本操作：

①比较关键码大小

②挪移记录

(5)对于待排序的记录序列，有三种常见的存储表示方法。

①向量结构，即将待排序的记录存放在一组地址连续的存储单元中。

②链表结构。

③记录向量与地址向量结合，即将待排序记录存放在一组地址连续的

存储单元中，同时另设一个指示各个记录位置的地址向量。

为简单起见，数据的存储结构采取向量的存储结构：

#definen20〃记录数

typedefintkeytype;

typedefstruct{

keytypekey;

datatypeother;

}rectype;rectyrp[en+l];

(6)排序算法的评价：

①算法的执行时间

②算法执行时所需的附加空间

10.2插入排序

基本原理：

每步将一个待排序的对象，按其关键字大小，插入到前面己经排好序的

一组对象适当位置上，直到对象全部插入为止。

10.2.1直接插入排序

1直接插入排序的基本思想

先假定第1个记录为有序序列，然后从第2条记录开始，挨次将记录插

入到前面已经有序的序列中，直至全部记录有序。

普通情况下，第i趟宜接插入排序：将r⑴插入到己经有序的序列

中，使其变成有序序列叩.用。

整个排序进行n-l趟插入。

2示例:

初始：|49]38659776132749

3算法:

voidInsertSort(rectypeR[],intn){

intij;

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

R[0]=R[i];

for(j=i-1;R[0].key<R|j].key;j-)

R[j+i]=RUI；

RU+1]=R[0]

)

)

4算法分析：

空间效率；只需要一个记录的辅助空间。

时间效率：

比较记录的次数为：

最小：上1次；最大:(n+2)(n-l)/2次

挪移记录的次数：

最小：2(n-l)最大:(n+4)(n-l)/2

平均情况：0(m)

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+l;i<=n;i++){

r[0]=r[i];

for(j=i-dk;(j>0&&R[j].key>r[0].key);j-=dk)

r[j+dk]=r[j];

Rlj+dk尸r[0];

)

)

)

2、算法分析：

Shell排序的平均比较次数和平均挪移次数都为0(nl.3)摆布

Shell排序算法中增加了一个辅助空间。

Shell排序是不稳定的。

10.3交换排序

交换排序基本思想：

两两比较待排序记录的排序码，交换不满足排序要求的偶对，直到全部

有序。

10.3.1冒泡排序(BubbleSort)

1、基本思想：

设待排序记录顺序存放在g,《中：

挨次比较(R,R,),(R,R)JR3),不满足顺序则交换，结果，最大者

在R中。这叫一次起泡。

此后，再对“存放在R,R,R,,R中n-1个记录作同样处理,结果，最大

123n-1

者在R中。

O

n-1次起泡能完成排序。设置标志noswap表示本次起泡是否有交换，若

无交换，表示排序完成。

2、示例：

3、算法：

voidbubbleSort(rectypeR[],intn){

i=l;flag=l;

for(i=l;i<n&&flag;i++){

flag=0;

for(j=l;j<=n-i;j++)

if(R[j].key>R[j+l].key)(

temp=R[j+l]；

RLi+i]=R|j];

R[j]=temp;

flag=1；

)

)

)

4、算法分析：

起泡排序的最坏时间复杂度为0(n2),平均时间复杂度为0(n2)»

起泡排序算法中增加一个辅助空间temp,辅助空间为S(n)=O(l)。

起泡排序是稳定的。

10.3.2快速排序(QuickSort)

1、基本思想：

快速排序的基本思想是：从待排序记录序列中选取一个记录(通常选取

第一个记录)作为“枢轴”，通过一趟排序(一次划分)将待排记录分割

成独立的两部份，其中一部份记录的关键字比枢轴小，另一部份记录

的关键字比枢轴大。然后则可分别对这两部份记录继续进行划分，以达

到整个序列有序。

1基本思想：

一趟快速排序(一次划分)的具体做法是：

附设两个指针low和high,它们的初值分别是一个序列的第一个和最后一

个记录的位置,设枢轴记录的关键字为pivotKey,在首先从high所指位置

起向前搜索直到第一个关键字小于pivotKey的记录和枢轴记录交换，然

后从low所指位置起向后搜索，找到第一个关键字大于pivotKey的记录和

枢轴记录互相交换，重复交替这两步直到k)w=high为止。

2、示例：

设记录的关键码序列为：

4938659776132749

对其进行快速排序。

3、算法：

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<high)&&(R[low].key<=pivotkey))

++10W；

r[high]=r[Iow];

)

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+l,high);

)

}

voidQuickSort(rectypeR||,intn){

QSort(R,n,l,n);

)

4、算法分析：

谡坏情况下，即当初始序列已经有序时，快速排序退化为起泡排序，为

0(112)。

最好时间复杂度为O(nlogn)o

平均时间复杂度是T(n)=O(nlogn)o

算法需要一个栈空间实现递归「栈的大小取决于递归调用的深度，最多

不超过n,理想情况下不超过logn：所以快速排序的辅助空间最坏为

S(n)=O(n),最好为S(n)=O(logn)o

快速排序是不稳定的。

10.4选择排序

选择排序(SelectionSort)的基本思想是：每一趟在n-i+l(i=L2,n-1)

个记录中选取关键字最小的记录作为有序序列中第i个记录。

10.4.1简单选择排序(SimpleSelectionSort)

1、基本思想：

第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出

关键字最小的记录，并和第i个记录进行交换。共需进行i-1趟比较，直

到所有记录排序完成为止。

2、示例：

3、算法：

voidSelectSort(rectypeR[],intn){

for(i=l;i<=n-l;i++){

k=i;

for(j=i+1;j<=n;j++)

if(R[j].key<R[k].key)k=j;

if(k!=i){

temp=R[i];

R[i]=R[k];

R|k]=temp;

)

)

4、算法分析：

直接选择排序的比较次数与文件初始状态无关。

直接选择排序的时间复杂度：

挪移：最好：0最坏：3(n-1)

比较：n(n-l)Z2

总的时间复杂度：0(n2)

稳定性：不稳定

10.4.2树形选择排序(TreeSelectionSort)

1基本思想：

简单选择排序的主要操作是比较，要提高它的速度必须减少比较的次数。

而实际上如果能利用以前的比较结果则可以提高排序速度。

树形选择排序(TreeSelectionSort),又称锦标赛排序(Tournamentsort),

其方法是：首先对n个记录的关键字进行两两比较，然后在n/2个较小

者之间再进行两两比较，如此重复直到选出最小关键字的记录为止。

然后对剩下的记录作同样的操作，选出具有次小关键字的记录。这个

过程可以用一个彻底二叉树来表示。

2示例：

3算法分析：

在树型选择排序中，含有n个叶子节点的彻底二叉树的深度为「log2nl+1，

则在树型选择排序中，每选择一个小关键字需要进行「log2n1次比较，

因此其时间复杂度为O(nlog2n)。挪移记录次数不超过比较次数，故总的

算法时间复杂度为O(nlog2n)。

缺点是使用了较多的辅助空间(n-1),并且和“最大值”进行了多余的比较。

10.4.3堆排序(HeapSort)

1堆的定义：

堆排序是对树型选择排序的进一步改进。采用堆排序时，只需要一个记

录大小的辅助空间。

1964年Willioms提出了堆排序。

堆的定义：n个元素的序列｛k,k,,k｝当且仅当满足如下关系时，称之

I2n

为堆。

kkkk

i2ii2i

kkkk

i2H-1i2i+l

(i=l,2,,n/2)

若将和此序列对应的一维数组看成是一个彻底二叉树，则堆的含义表明，

彻底二叉树中所有非终端结点的值均不小于(或者不大于)其摆布孩子结

点的值。

2堆排序的基本思想：

若序列｛k(k,,k)是堆，则堆顶元素必为序列中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

3算法：

voidSift(rectypeR[],ints;intm){〃筛选算法

temp=R[s];

for(j=2*s;j<=m;j*=2){

if((j<m)&&(R[j].key<R[j+l|.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>=l;i・・)〃初始建堆

Sift(R,i,n);

for(i=n;i>l;i-){

temp=R[l];R[l]=R[i];

R[i]=temp;

Sift(R,l,i-l);

)

)

4算法分析：

初始建堆比较次数为：O(n)

排序中比较次数为：<0(n*Iog2n)0

挪移次数小于比较次数。

在最坏的情况下，时间复杂度也是O(nlogn)。

且仅需一个记录大小的辅助空间。

堆排序合用于n值较大的情况。

堆排序是不稳定的排序方法。

10.5归并排序

1基本思想：

归并的含义是将两个或者两个以上的有序表合并成一个有序表。利用归

并的思想就可以实现排序。假设初始的序列含有n个记录，可以看成n

个有序的子序列，每一个子序列的长度为1,然后两两归并，得到n/2

个长度为2或者1的有序子序列；再两两归并，如此重复直到得到一个长度

为n的有序序列为止。这种排序方法称为二路归并排序。

2示例：

voidMerge(rectypeR[],rectypeR1[],intlow,intmid,inthigh){

i=low;j=mid+l;k=low;

while((i<=mid)&&(j<=high))

if(R[i].key<=R[j].key)Rl[k++]=R[i++];

elseRl[k++]=R[j++];

while(j<=mid)Rl[k++]=R[i4-+];

while(j<=high)RI[k++]=R[j4-+];

\

]

voidMSort(rectypeR|],rectypeRl[],ints,intt){

if(s==t)rl[s]=r[s];

else{

m=(s+t)/2;

MSort(R,R2,s,m);

MSort(R,R2,m+l,t);

Merge(r2,rl,s,m,t);

)

voidMergeSort(rectypeR[],intn){

MSort(rj,l,n);

)

时间复杂度:O(nlogn)

空间复杂度:和待排出录等量的空间.

二路归并算法是稳定的.

普通情况下很少用于内部排序.

10.6分配排序

分配类排序则利用分配和采集两种基本操作，基数类排序就是典型的分

配类排序。

分配排序的思想是把排序码分解成若干部份，然后通过对各个部份排序

码的分别排序，最终达到整个排序码的排序。

10.6.1概述

普通情况下，假设文件F有n个记录

F=(R,R,„R)

01n-l

且每一个记录R.的排序码中含有d个部份(k。，kk),则文件F

11011id-1

对排序码(k,k,,,,k)有序是指：文件中任意两个记录R和R(0WiW

jW

01d-1ij

不谪足词典次序有序关系

(k/k,i；<(k.o，k,晨)

其中k称为最高位排序码，k,称为最低位排序码。实现分配排序，有两

种方点：第一种是先对最高检'排序码k排序，称为最高位优先法(Most

0

SignificantDigitfirst)。第二种是先对最低位排序码k排序，称为

d-l

最低位优先法(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叠牌按花色的次序采集到一起，于是就得到了有序

序列。

低位优先法比高位优先法简单，高位优先排序必须将文件逐层分割成若

干子文件，然后各子文件独立排序；低位优先排序不必分成子堆，对每

个排序码都是整个文件参加排序，且可通过若干次“分配”和“采集”

实现排序。但对K(0<=i<=d-2)进行排序时，只能用稳定的排序方法。

下面将介绍的基数排序就是用排序码低位优先法的思想对排序码进行分解

后排序的一种方法。

10.6.2链式基数排序

采用基数排序首先把每一个排序码看成是一个d元组：

K=(K,K.„,K)

110i1id-1

其中每一个K都是集合{C,C,C}(C<C<„<C)中的值，即CWK

i01r-101r-l0ij

WC(0WiWnT,0WjWdT),其中r称为基数。排序时先按K从小

r-|