最新【考研计算机专业课】武汉大学数据结构PPT课件 第10章内排序(共88张PPT课件).pptx

《最新【考研计算机专业课】武汉大学数据结构PPT课件 第10章内排序(共88张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】武汉大学数据结构PPT课件 第10章内排序(共88张PPT课件).pptx（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第10章章 内内 排排 序序10.6 基数排序基数排序10.1 排序排序(pi x)的基本概念的基本概念10.2 插入排序插入排序10.3 交换交换(jiohun)排序排序10.4 选择选择(xunz)排序排序10.5 归并排序归并排序10.7 各种内排序方法的比较和选择各种内排序方法的比较和选择第一页，共八十八页。10.1 排序的基本概念排序的基本概念 所谓排序所谓排序,就是要整理表中的记录就是要整理表中的记录,使之按关键字递增使之按关键字递增(或递减或递减)有序排列有序排列(pili)。其确切定义如下：。其确切定义如下： 输入：输入：n个记录个记录,R0,R1,Rn-1,其相应的关键字分

2、别为其相应的关键字分别为k0,k1,kn-1。 输出：输出：Ri , 0,Ri , 1,Ri , n - 1,使得使得ki , 0ki , 1ki , n - 1 (或或ki,0ki,1ki,n-1)。本章仅考虑递增本章仅考虑递增(dzng)排序排序第二页，共八十八页。 当待排序记录的关键字均不相同时，排序的结果是惟一的当待排序记录的关键字均不相同时，排序的结果是惟一的, ,否则排否则排序的结果不一定唯一。如果待排序的表中序的结果不一定唯一。如果待排序的表中, ,存在有多个关键字相同的记存在有多个关键字相同的记录录, ,经过排序后这些具有相同关键字的记录之间的相对次序保持不变经过排序后这些具有

3、相同关键字的记录之间的相对次序保持不变, ,则称这种排序方法是则称这种排序方法是稳定稳定(wndng)(wndng)的；反之的；反之, ,若具有相同关键字的记录若具有相同关键字的记录之间的相对次序发生变化之间的相对次序发生变化, ,则称这种排序方法是则称这种排序方法是不稳定不稳定的。的。 在排序过程中，若整个表都是放在内存中处理，排序时不涉及数在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据据(shj)的内、外存交换，则称之为的内、外存交换，则称之为内排序内排序；反之，若排序过程中；反之，若排序过程中要进行数据的内、外存交换，则称之为要进行数据的内、外存交换，则称之为外排序外排序。

4、算法算法(sun f)的稳定性的稳定性内排序和外排序内排序和外排序第三页，共八十八页。内排序的基本内排序的基本(jbn)方法方法内部排序内部排序(pi x)的过程是一个逐步扩大记录的有序序列的过程是一个逐步扩大记录的有序序列长度的过程。长度的过程。经过经过(jnggu)一趟排一趟排序序有序序列区无 序 序 列 区有序序列区无 序 序 列 区第四页，共八十八页。正序和反序正序和反序若待排序的表中元素已按关键字排好序，称此表中元素为正若待排序的表中元素已按关键字排好序，称此表中元素为正序；反之，若待排序的表中元素的关键字顺序正好序；反之，若待排序的表中元素的关键字顺序正好(zhngho)和排好和排

5、好序的顺序相反，称此表中元素为反序。序的顺序相反，称此表中元素为反序。排序的分类排序的分类根据排序算法是否基于关键字的比较，将排序算法分为基于比较根据排序算法是否基于关键字的比较，将排序算法分为基于比较的排序算法和不基于比较的排序算法。像插入排序、交换排序、选择的排序算法和不基于比较的排序算法。像插入排序、交换排序、选择(xunz)排序和归并排序都是基于比较的排序算法；而基数排序是不基排序和归并排序都是基于比较的排序算法；而基数排序是不基于比较的排序算法。于比较的排序算法。第五页，共八十八页。 待排序的顺序表类型待排序的顺序表类型(lixng)的类型的类型(lixng)定义如下：定义如下： t

6、ypedef int KeyType; /定义关键字类型定义关键字类型 typedef struct /记录类型记录类型 KeyType key; /关键字项关键字项 InfoType data; /其他数据项其他数据项,类型为类型为InfoType RecType; /排序的记录类型定义排序的记录类型定义 存放数据的结构存放数据的结构(jigu)：第六页，共八十八页。10.2 插入排序插入排序 插入排序的基本思想是：每次将一个待排序的记录插入排序的基本思想是：每次将一个待排序的记录, ,按其关键字按其关键字大小插入到前面已经排好序的子表中的适当位置大小插入到前面已经排好序的子表中的适当位置,

7、 ,直到全部记录插入直到全部记录插入完成为止完成为止(wizh)(wizh)。 两种插入排序方法：两种插入排序方法： （1 1）直接插入排序（含二分插入排序）直接插入排序（含二分插入排序） （2 2）希尔排序）希尔排序第七页，共八十八页。10.2.1 直接插入排序直接插入排序 假设待排序的记录存放在数组假设待排序的记录存放在数组R0.n-1中，排序过程的某一中，排序过程的某一中间时刻，中间时刻，R被划分成两个子区间被划分成两个子区间R0.i-1和和Ri.n-1，其中：前，其中：前一个一个(y )子区间是已排好序的有序区，后一个子区间是已排好序的有序区，后一个(y )子区间则是当子区间则是当前未

8、排序的部分，不妨称其为无序区。前未排序的部分，不妨称其为无序区。 直接插入排序的基本操作是将当前无序区的第直接插入排序的基本操作是将当前无序区的第1个记录个记录Ri插入到有序插入到有序区区R0.i-1中适当的位置上，使中适当的位置上，使R0.i变为新的有序区。这种方法通常称为变为新的有序区。这种方法通常称为增量法增量法，因为它每次使有序区增加，因为它每次使有序区增加1个记录。个记录。 第八页，共八十八页。 R0Ri-1 有序区有序区 RiRn-1 无序区无序区 一趟排序一趟排序 R0Ri-1 Ri Ri+1Rn-1 有序区有序区 无序区无序区 第九页，共八十八页。R0jRij=i-1插入插入(

9、ch r)位置位置在有序区中插入在有序区中插入(ch r)Ri的过程的过程第十页，共八十八页。void InsertSort(RecType R,int n) /对对R0.n-1按递增有序进行按递增有序进行(jnxng)直接插入排序直接插入排序 int i,j;RecType temp; for (i=1;i=0 & temp.keyj且且Ri.key=Rj.key时，本算法将时，本算法将Ri插入在插入在Rj的后面的后面(hu mian)，使，使Ri和和Rj的相对位置保持不变，所以直接插的相对位置保持不变，所以直接插入排序是一种稳定的排序方法。入排序是一种稳定的排序方法。第十四页，共八十八页。

10、10.2.2 二分二分(r fn)插入排序插入排序查找采用查找采用(ciyng)二分查找方法，称为二分插入排序或折半插入排序。二分查找方法，称为二分插入排序或折半插入排序。void InsertSort1(RecType R,int n)int i,j,low,high,mid; RecType tmp; for (i=1;in;i+) tmp=Ri; /将将Ri保存到保存到tmp中中low=0;high=i-1;while (low=high) /在在Rlow.high中查找插入的位置中查找插入的位置 mid=(low+high)/2;/取中间位置取中间位置 if (tmp.key=high

11、+1;j-)/记录后移记录后移 Rj+1=Rj;Rhigh+1=tmp;/插入插入 第十五页，共八十八页。10.2.3 希尔排序希尔排序 希尔排序也是一种插入排序方法希尔排序也是一种插入排序方法,实际上是一种分组插入方法。实际上是一种分组插入方法。 基本思想：基本思想： 先取定一个小于先取定一个小于n的整数的整数d1作为第一个增量，把表的全部记录分成作为第一个增量，把表的全部记录分成d1个组，所有距离个组，所有距离(jl)为为d1的倍数的记录放在同一个组中，在各组内的倍数的记录放在同一个组中，在各组内进行直接插入排序；进行直接插入排序； 然后然后,取第二个增量取第二个增量d2（d1），重复上述

12、的分组和排序，直至），重复上述的分组和排序，直至所取的增量所取的增量dt=1（dtdt-1d20) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /Rj与与Rj+d交换交换(jiohun) Rj=Rj+d;Rj+d=temp; j=j-d; d=d/2; /递减增量递减增量d 第十九页，共八十八页。 例例10.2 设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用说明采用(ciyng)希尔排序方法进行排序的过程。希尔排序方法进行排序的过程。 9 8 7 6 5 4 3 2 1 0 初始状态

13、初始状态 (连线部分为下一趟作准备连线部分为下一趟作准备) 4 3 2 1 0 9 8 7 6 5 d=5 (d=5 执行结果执行结果) 0 1 2 3 4 5 6 7 8 9 d=2 (d=2 执行结果执行结果) 0 1 2 3 4 5 6 7 8 9 d=1 (d=1 执行结果执行结果) 第二十页，共八十八页。希尔排序的时间复杂度约为希尔排序的时间复杂度约为O(n1.3)。为什么希尔排序比直接插入排序好？为什么希尔排序比直接插入排序好？例如例如(lr)：有：有10个元素要排序。个元素要排序。希尔排序希尔排序(pi x)直接直接(zhji)插入排插入排序序大约时间大约时间=102=100d=

14、5：分为：分为5组，时间约为组，时间约为5*2220d=2：分为：分为2组，时间约为组，时间约为2*5250d=1：分为：分为1组，几乎有序，时间约为组，几乎有序，时间约为1080第二十一页，共八十八页。希尔排序算法不稳定的反例希尔排序算法不稳定的反例希尔排序法是一种不稳定的排序算法。希尔排序法是一种不稳定的排序算法。例如，若希尔排序分为两组：例如，若希尔排序分为两组：3,10,7,8,20和和5,8,2,1,6，显然，第，显然，第1组的组的8排列排列(pili)在第在第2组的组的8的后面，两组采用直接插入排序后的结果的后面，两组采用直接插入排序后的结果为：为：3,7,8,10,20和和1,2

15、,5,6,8，这样第，这样第1组的组的8排列到第排列到第2组的组的8的前的前面，它们的相对位置发生了改变。面，它们的相对位置发生了改变。第二十二页，共八十八页。思考题：思考题：希尔排序希尔排序(pi x)中的有序区是全局有序吗？中的有序区是全局有序吗？第二十三页，共八十八页。10.3 交换交换(jiohun)排序排序 交换排序的基本思想：两两比较待排序记录的关键字交换排序的基本思想：两两比较待排序记录的关键字,发现两个记录发现两个记录的次序相反时即进行交换的次序相反时即进行交换,直到没有反序的记录为止。直到没有反序的记录为止。 两种交换排序两种交换排序: （1）冒泡排序）冒泡排序 （2）快速排

16、序）快速排序第二十四页，共八十八页。10.3.1 冒泡排序冒泡排序 冒泡排序的基本思想冒泡排序的基本思想：通过无序区中相邻记录关键字间的比：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上较和位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮漂浮”直至直至(zhzh)“水面水面”。 整个算法是从最下面的记录开始，对每两个相邻的关键字进行整个算法是从最下面的记录开始，对每两个相邻的关键字进行比较比较,且使关键字较小的记录换至关键字较大的记录之上，使得经且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着再在

17、剩下过一趟冒泡排序后，关键字最小的记录到达最上端，接着再在剩下的记录中找关键字次小的记录，并把它换在第二个位置上。依次类的记录中找关键字次小的记录，并把它换在第二个位置上。依次类推，一直到所有记录都有序为止。推，一直到所有记录都有序为止。第二十五页，共八十八页。 一趟排序一趟排序 R0 有序区有序区 无序区无序区 Ri-1 Ri Rn-1 Ri+1 R0 Ri Ri-1 将无序区中将无序区中最小记录放最小记录放在在 Ri Ri+1 Rn-1 有序区有序区 无序区无序区 第二十六页，共八十八页。void BubbleSort(RecType R,int n) int i,j;RecType te

18、mp; for (i=0;ii;j-) /比较找本趟最小关键字的记录比较找本趟最小关键字的记录(jl) if (Rj.keyRj-1.key) temp=Rj; /Rj与与Rj-1进行交换进行交换 Rj=Rj-1; Rj-1=temp; 第二十七页，共八十八页。 例例10.3 设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用冒泡排序方法说明采用冒泡排序方法(fngf)进行排序的过程。进行排序的过程。 初始关键字初始关键字 9 8 7 6 5 4 3 2 1 0 i=0 0 9 8 7 6 5 4 3 2 1 i=1 0

19、1 9 8 7 6 5 4 3 2 i=2 0 1 2 9 8 7 6 5 4 3 i=3 0 1 2 3 9 8 7 6 5 4 i=4 0 1 2 3 4 9 8 7 6 5 i=5 0 1 2 3 4 5 9 8 7 6 i=6 0 1 2 3 4 5 6 9 8 7 i=7 0 1 2 3 4 5 6 7 9 8 i=8 0 1 2 3 4 5 6 7 8 9 第二十八页，共八十八页。思考题：思考题：冒泡冒泡排序排序(pi x)中的有序区是全局有序吗？中的有序区是全局有序吗？第二十九页，共八十八页。 在有些情况下，在第在有些情况下，在第i（in-1）趟时已排好序了，但仍执行）趟时已排好

20、序了，但仍执行后面几趟的比较。实际上，一旦算法中某一趟比较时不出现记后面几趟的比较。实际上，一旦算法中某一趟比较时不出现记录交换录交换,说明已排好序了，就可以结束本算法。说明已排好序了，就可以结束本算法。 为此为此(wi c)得到改进冒泡排序算法如下：得到改进冒泡排序算法如下：第三十页，共八十八页。void BubbleSort(RecType R,int n) int i,j,exchange;RecType temp; for (i=0;ii;j-)/比较比较(bjio),找出最小关键字的找出最小关键字的记录记录 if (Rj.keyRj-1.key) temp=Rj; Rj=Rj-1;R

21、j-1=temp; exchange=1; if (exchange=0) return; /中途结束算法中途结束算法 第三十一页，共八十八页。最好的情况最好的情况(qngkung)（关键字在记录序列中顺序有序）：（关键字在记录序列中顺序有序）： 只需进行一趟冒泡只需进行一趟冒泡“比较比较(bjio)”的次数：的次数：最坏的情况（关键字在记录最坏的情况（关键字在记录(jl)序列中逆序有序）：序列中逆序有序）： 需进行需进行n-1趟冒泡趟冒泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-121110)n(n)in(ni 2131320)n(n)in(n

22、i 第三十二页，共八十八页。10.3.2 快速排序快速排序 快速排序是由冒泡排序改进而得的。快速排序是由冒泡排序改进而得的。 基本思想基本思想(sxing)(sxing)：在待排序的：在待排序的n n个记录中任取一个记录个记录中任取一个记录( (通常取第一通常取第一个记录个记录) )，把该记录放入适当位置后，把该记录放入适当位置后, ,数据序列被此记录划分成两部分。所数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分有关键字比该记录关键字小的记录放置在前一部分, ,所有比它大的记录放所有比它大的记录放置在后一部分置在后一部分, ,并把该记录排在这两部分的中间并把该记录

23、排在这两部分的中间( (称为该记录归位称为该记录归位) )，这个，这个过程称作一趟快速排序。过程称作一趟快速排序。 第三十三页，共八十八页。 首先首先(shuxin)对无序的记录序列进行对无序的记录序列进行“一次划分一次划分”，之后分别对分割所得两，之后分别对分割所得两个子序列个子序列“递归递归”进行快速排序。进行快速排序。无 序 的 记 录 序 列无序记录(jl)子序列(1)无序(w x)子序列(2)基准基准一次划分分别进行快速排序需要确定排序的序列，采用什么存储结构？需要确定排序的序列，采用什么存储结构？第三十四页，共八十八页。52 49 80 36 14 58 61 97 23 75st

24、lowhigh设设 Rs=52 为枢轴为枢轴(sh zhu) 将将 Rhigh.key 和基准的关键字进行比较和基准的关键字进行比较(bjio)，要求，要求Rhigh.key 基基准的关键字准的关键字 将将 Rlow.key 和基准和基准(jzhn)的关键字进行比较，要求的关键字进行比较，要求Rlow.key 基基准的关键字准的关键字high23low80high14low52例如例如R052lowhighhighhighlow第三十五页，共八十八页。 可见，经过可见，经过(jnggu)“一次划分一次划分” ，将关键字序列，将关键字序列 52, 49, 80, 36, 14, 58, 61,

25、97, 23, 75 调整为调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整在调整(tiozhng)过程中，设立了两个指针：过程中，设立了两个指针： low 和和high，它们的初值分，它们的初值分别为：别为： s 和和 t。 之后逐渐减小之后逐渐减小 high，增加，增加(zngji) low，并保证，并保证 Rhigh.key52，和，和 Rlow.key52, ,否则进行记录的否则进行记录的“交换交换”。第三十六页，共八十八页。 以后对所有的两部分分别重复上述过程，直至每部分内只有以后对所有的两部分分别重复上述过程，直至每部分内只有一个记录

26、为止。一个记录为止。简而言之，每趟使表的简而言之，每趟使表的第一个元素第一个元素放入适当位置，将表一放入适当位置，将表一分为二分为二(y fn wi r)，对子表按递归方式继续这种划分，直至划分的子，对子表按递归方式继续这种划分，直至划分的子表长为表长为1。第三十七页，共八十八页。void QuickSort(RecType R,int s,int t) /对对Rs至至Rt的元素的元素(yun s)进行快速排序进行快速排序 int i=s,j=t;RecType temp; if (si & Rj.keytemp.key) j-; Ri=Rj; while (ij & Ri.keytemp.k

27、ey) i+; Rj=Ri; Ri=temp; QuickSort(R,s,i-1); /对左区间递归排序对左区间递归排序 QuickSort(R,i+1,t); /对右区间递归排序对右区间递归排序 划分划分(hu fn)第三十八页，共八十八页。 例例 1 0 . 4 设 待 排 序 的 表 有设 待 排 序 的 表 有 1 0 个 记 录个 记 录 , 其 关 键 字 分 别 为其 关 键 字 分 别 为6,8,7,9,0,1,3,2,4,5。说明。说明(shumng)采用快速排序方法进行排序的过采用快速排序方法进行排序的过程。程。 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0

28、 1 6 9 7 8 (a) 第 1 次划分 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 (b) 第 2 次划分 1 4 2 3 0 5 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2 3 4 (c) 第 3 次划分 (d) 第 4 次划分 第三十九页，共八十八页。 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2

29、3 0 5 0 1 2 3 4 2 3 4 (e) 第 5 次划分 3 4 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2 3 4 (f) 第 6 次划分 3 4 8 7 9 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 0 1 2 3 4 2 3 4 (g) 第 7 次划分 3 4 8 7 9 7 8 第四十页，共八十八页。nkavgavgavgknTkTnCnnT1)() 1(1)(则可得结果则可得结果(ji gu)：结论结论(jiln): 快速排序的时

30、间复杂度为快速排序的时间复杂度为O(nlog2n)由此可得快速排序由此可得快速排序(pi x)所需时间的平均值为：所需时间的平均值为：平均所需栈空间为平均所需栈空间为O(log2n)。nk-1n-k1次划分的时间次划分的时间Tavg(n)=Cnlog2n。第四十一页，共八十八页。10.4 选择排序选择排序 选择排序的基本选择排序的基本(jbn)思想是：每一趟从待排序的记录中选出关键字最思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。 两种选择排序方法：两种选择排序方法： （1）

31、直接选择排序）直接选择排序(或称简单选择排序或称简单选择排序) （2）堆排序）堆排序第四十二页，共八十八页。10.4.1 直接选择排序直接选择排序基本思想：第基本思想：第i趟排序开始时趟排序开始时,当前有序区和无序区分别当前有序区和无序区分别(fnbi)为为R0.i-1和和Ri.n-1（0in-1），该趟排序则是从当前无序区中选出），该趟排序则是从当前无序区中选出关键字最小的记录关键字最小的记录Rk，将它与无序区的第，将它与无序区的第1个记录个记录Ri交换，使交换，使R0.i和和Ri+1.n-1分别分别(fnbi)变为新的有序区和新的无序区。变为新的有序区和新的无序区。 第四十三页，共八十八页

32、。假设排序过程中，待排记录假设排序过程中，待排记录(jl)序列的状态为：序列的状态为：有序序列有序序列(xli)R1.i-1无序无序(w x)序列序列 Ri.n 第第 i 趟趟简单选择排序简单选择排序从中选出关键字最小的记录有序序列有序序列R1.i无序序列无序序列 Ri+1.n第四十四页，共八十八页。void SelectSort(RecType R,int n) int i,j,k; RecType temp; for (i=0;in-1;i+) /做第做第i趟排序趟排序 k=i;for (j=i+1;jn;j+) /在在i.n-1中选中选key最小的最小的Rk if (Rj.keyRk.k

33、ey) k=j; /k记下记下(j xi)的最小关键字所在的位置的最小关键字所在的位置if (k!=i) /交换交换Ri和和Rk temp=Ri; Ri=Rk; Rk=temp; 第四十五页，共八十八页。 例例10.5 设待排序的表有设待排序的表有10个记录个记录(jl),其关键字分别为其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用直接选择排序方法进行排序的过程。说明采用直接选择排序方法进行排序的过程。 初始关键字初始关键字 6 8 7 9 0 1 3 2 4 5 i=0 0 8 7 9 6 1 3 2 4 5 i=1 0 1 7 9 6 8 3 2 4 5 i=2 0 1 2

34、 9 6 8 3 7 4 5 i=3 0 1 2 3 6 8 9 7 4 5 i=4 0 1 2 3 4 8 9 7 6 5 i=5 0 1 2 3 4 5 9 7 6 8 i=6 0 1 2 3 4 5 6 7 9 8 i=7 0 1 2 3 4 5 6 7 9 8 i=8 0 1 2 3 4 5 6 7 8 9 第四十六页，共八十八页。 对对 n 个记录进行简单个记录进行简单(jindn)选择排序，所需进行的选择排序，所需进行的 关键字间关键字间的比较次数的比较次数 总计为：总计为：移动移动(ydng)记录的次数，最小值为记录的次数，最小值为 0, 最大值为最大值为3(n-1) 。2112

35、0)n(n)in(ni 第四十七页，共八十八页。10.4.2 堆排序堆排序 堆排序是一树形选择排序，它的特点是，在排序过程中，将堆排序是一树形选择排序，它的特点是，在排序过程中，将R1.n看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点(ji din)和孩子结点和孩子结点(ji din)之间的内在关系，在当前无序区中选择关键字最大之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。（或最小）的记录。 堆的定义是：堆的定义是：n个关键字序列个关键字序列K1,K2,Kn称为称为堆堆,当且仅当该序列满足当且仅当该序列满

36、足如下性质（简称为堆性质）：如下性质（简称为堆性质）： （1）KiK2i 且且 KiK2i+1 或或 （2）KiK2i 且且 KiK2i+1（1i n/2 ） 满足第（满足第（1）种情况的堆称为小根堆，满足第（）种情况的堆称为小根堆，满足第（2）种情况的堆称）种情况的堆称为大根堆。下面讨论的堆是大根堆。为大根堆。下面讨论的堆是大根堆。第四十八页，共八十八页。12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49是小根堆是小根堆例如例如(lr):12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是不是(b shi)堆堆第四十九页，

37、共八十八页。rir2i r2i+1 若将该数列视作完全若将该数列视作完全(wnqun)二叉树，则二叉树，则 r2i 是是 ri 的左孩子；的左孩子； r2i+1 是是 ri 的右孩子。的右孩子。1236276549817355403498例如例如(lr):是堆是堆14不不第五十页，共八十八页。 堆排序的关键是构造堆堆排序的关键是构造堆,这里采用筛选算法建堆。这里采用筛选算法建堆。 所谓所谓“筛选筛选”指的是，对一棵左指的是，对一棵左/右子树均为堆的完全二叉树，右子树均为堆的完全二叉树，“调整调整”根结点使整个二叉树也成为根结点使整个二叉树也成为(chngwi)一个堆。一个堆。堆堆筛选筛选(sh

38、ixun)堆堆第五十一页，共八十八页。98814973556412362740例如例如(lr):是大根堆是大根堆12但在但在 98 和和 12 进行进行(jnxng)互换之后，它就不是堆了，互换之后，它就不是堆了，因此因此(ync)，需要对它进行，需要对它进行“筛选筛选”。98128173641298比较比较比较比较第五十二页，共八十八页。void sift(RecType R,int low,int high) /调整堆的算法调整堆的算法 int i=low,j=2*i; /Rj是是Ri的左孩子的左孩子 RecType temp=Ri; while (j=high) if (jhigh &

39、Rj.keyRj+1.key) j+; if (temp.key=1;i-) /循环建立初始堆循环建立初始堆 sift(R,i,n); for (i=n;i=2;i-) /进行进行n-1次循环次循环,完成推排序完成推排序(pi x) temp=R1; /将第一个元素同当前区间内将第一个元素同当前区间内R1对换对换 R1=Ri;Ri=temp; sift(R,1,i-1); /筛选筛选R1结点结点,得到得到i-1个结点的堆个结点的堆 第五十四页，共八十八页。 例 设 待 排 序 的 表 有例 设 待 排 序 的 表 有 1 0 个 记 录个 记 录 , 其 关 键 字 分 别 为其 关 键 字

40、分 别 为6,8,7,9,0,1,3,2,4,5。说明采用堆排序方法进行。说明采用堆排序方法进行(jnxng)排序的过程。排序的过程。 6 8 7 9 0 2 4 1 3 5 9 8 7 6 5 2 4 1 3 0 (a) 初始状态初始状态 (b) 建立的初始堆建立的初始堆 第五十五页，共八十八页。 0 8 7 6 5 2 4 1 3 8 6 7 4 5 2 0 1 3 (a) 交换交换 9 与与 0，输出，输出 9 (b) 筛选调整筛选调整 0 6 7 4 5 2 1 3 (c) 交换交换 8 与与 0，输出，输出 8 7 6 3 4 5 2 1 0 2 6 3 4 5 1 0 (d) 筛选

41、调整筛选调整 (e) 交换交换 7 与与 2，输出，输出 7 6 5 3 4 2 1 0 (f) 筛选调整筛选调整 堆排序过程堆排序过程(guchng)：第五十六页，共八十八页。 0 5 3 4 2 1 5 4 3 0 2 1 (g) 交换交换 6 与与 0，输出，输出 6 (h) 筛选调整筛选调整 (i) 交换交换 5 与与 1，输出，输出 5 1 4 3 0 2 4 2 3 0 1 (j) 筛选调整筛选调整 1 2 3 2 3 2 0 (k) 交换交换 4 与与 1，输出，输出 4 (l) 筛选调整筛选调整 (m) 交换交换 3 与与 1，输出，输出 3 0 2 1 2 0 1 (n) 筛

42、选调整筛选调整 1 1 0 1 0 (o) 交换交换 2 与与 1，输出，输出 2 (p) 筛选调整筛选调整 (q) 交换交换 1 与与 0，输出，输出 1 0 1 0 (r) 输出输出 0 第五十七页，共八十八页。堆排序的时间堆排序的时间(shjin)复杂度分析：复杂度分析：1. 对深度为对深度为 k 的堆，的堆，“筛选筛选(shixun)”所需进行的关键字所需进行的关键字比较的次数至多为比较的次数至多为2(k-1)；3. 调整调整(tiozhng)“堆顶堆顶” n-1 次，总共进行的关键次，总共进行的关键 字比较的次数不超过字比较的次数不超过 2 ( log2(n-1) + log2(n-

43、2) + +log22) 2n( log2n ) 因此，堆排序的时间复杂度为因此，堆排序的时间复杂度为O(nlogn)。第五十八页，共八十八页。思考题：思考题：选择选择(xunz)排序中的有序区是全局有序吗？排序中的有序区是全局有序吗？第五十九页，共八十八页。10.5 归并排序归并排序 归并排序是多次将两个或两个以上的有序表合并成一个新归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的有序表。最简单(jindn)的归并是直接将两个有序的子表合并的归并是直接将两个有序的子表合并成一个有序的表。成一个有序的表。 第六十页，共八十八页。在内部排序中，通常采用的是在内部排序中，通常采

44、用的是2-路归并排序。即：将两个位置路归并排序。即：将两个位置(wi zhi)相邻的记录有序子序列。相邻的记录有序子序列。归并归并(gubng)为一个记录的有序序列。为一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列(xli) Rl.m有序子序列有序子序列 Rm+1.n这个操作对顺序表而言，是轻而易举的。这个操作对顺序表而言，是轻而易举的。第六十一页，共八十八页。void Merge(RecType R,int low,int mid,int high) RecType *R1; int i=low,j=mid+1,k=0; /k是是R1的下标的下标(xi bio),i

45、、j分别为第分别为第1、2段的下标段的下标(xi bio) R1=(RecType *)malloc(high-low+1)*sizeof(RecType); while (i=mid & j=high) if (Ri.key=Rj.key) /将第将第1段中的记录放入段中的记录放入R1中中 R1k=Ri; i+;k+; else /将第将第2段中的记录放入段中的记录放入R1中中 R1k=Rj; j+;k+; Merge()实现实现(shxin)了一次归并了一次归并 :空间空间(kngjin)复杂度为复杂度为O(high-low+1)第六十二页，共八十八页。while (i=mid) /将第将

46、第1段余下段余下(yxi)部分复制到部分复制到R1 R1k=Ri; i+;k+; while (j=high) /将第将第2段余下部分复制到段余下部分复制到R1 R1k=Rj; j+;k+; for (k=0,i=low;i=high;k+,i+) /将将R1复制回复制回R中中 Ri=R1k; free(R1); 第六十三页，共八十八页。void MergePass(RecType R,int length,int n) int i; for (i=0;i+2*length-1n;i=i+2*length) /归并归并length长的两相邻子表长的两相邻子表 Merge(R,i,i+lengt

47、h-1,i+2*length-1); if (i+length-1n) /余下余下(yxi)两个子表两个子表,后者长度小于后者长度小于length Merge(R,i,i+length-1,n-1); /归并这两个子表归并这两个子表MergePass()实现实现(shxin)了一趟归并了一趟归并 第六十四页，共八十八页。二路二路(r l)归并排序算法如下：归并排序算法如下：void MergeSort(RecType R,int n) int length; for (length=1;length=0;i-) /从低位到高位做从低位到高位做d趟排序趟排序 /123以以“321”存储存储 fo

48、r (j=0;jdatai-0; /找第找第k个链队个链队 if (headk=NULL) /进行分配进行分配(fnpi),即采用尾插法建立单链表即采用尾插法建立单链表 headk=p; tailk=p; else tailk-next=p; tailk=p; p=p-next; /取下一个待排序的元素取下一个待排序的元素 分分配配(fnpi)第八十页，共八十八页。 p=NULL; for (j=0;jnext=headj; t=tailj; t-next=NULL; /最后一个结点的最后一个结点的next域置域置NULL 收收集集(shuj)排序完成排序完成(wn chng)后，后，p指向的

49、是一个有序单链表指向的是一个有序单链表第八十一页，共八十八页。 例例 设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为75,23,98,44,57,12,29,64,38,82。说明采用基数排序方法。说明采用基数排序方法(fngf)进进行排序的过程。行排序的过程。 初初始始关关键键字字 75 23 98 44 57 12 29 64 38 82 按按个个数数排排序序 12 82 23 44 64 75 57 98 38 29 按按十十位位排排序序 12 23 29 38 44 57 64 75 82 98 第八十二页，共八十八页。 p 75 23 98 44 57 1

50、2 29 64 38 82 （a）初始状态）初始状态 head0 head1 head2 head3 head4 head5 head6 head7 head8 head9 tail0 tail1 tail2 tail3 tail4 tail5 tail6 tail7 tail8 tail9 12 82 23 75 57 29 44 64 98 38 链队头指针 链队尾指针 （b）按个位分配之后）按个位分配之后 p 12 82 23 44 64 75 57 98 38 29 （c）按个位收集之后）按个位收集之后 head0 head1 head2 head3 head4 head5 head6