九江学院《数据结构》第08章排序.ppt-淘文阁

资源描述

《九江学院《数据结构》第08章排序.ppt》由会员分享，可在线阅读，更多相关《九江学院《数据结构》第08章排序.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、退出主目录下一页第八章排序8.1 排序的基本概念8.2 插入类排序8.3 选择类排序8.4 交换类排序8.5 归并排序主目录下一页上一页退出本章要点n 排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列n 排序过程的组成步骤：n 首先比较两个关键字的大小n 然后将记录从一个位置移动到另一个位置n 排序的分类：n 根据排序过程中所使用的内、外存情况n内部排序n外部排序8.1 排序的基本概念主目录下一页上一页退出本章要点n 排序方法的稳定性：对于具有同一排序码的多个纪录来说，采用的排序方法使排序后的记录的相对次序是否发生变化n 没有发生变化排

2、序方法是稳定的n 发生了变化排序方法是不稳定的例如：排序前：（45，32，67，24，32，86）排序后：（24，32，32，45，67，86）是稳定的排序（24，32，32，45，67，86）是不稳定的排序8.1 排序的基本概念主目录下一页上一页退出本章要点n 向量结构：将待排序的记录存放在一组地址连续的存储单元中n 链表结构：记录之间逻辑上的相邻性是靠指针来维持的n 记录向量与地址向量结合：将待排序的记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量存储方法主目录下一页上一页退出本章要点20 10 7 30 5 19x520 10 7 30 19

3、 5 20 10 7 30 19x75 20 10 30 19 5 7 20 10 30 19x105 7 20 30 19 5 7 10 20 30 19x195 7 10 20 30 5 7 10 19 20 30 x205 7 10 19 20 30 x305 7 10 19 20 30记录结构主目录下一页上一页退出本章要点20head107 3020head107 30p7head2010 307head2010 30p7head1020 30链表结构主目录下一页上一页退出本章要点20 10 7 30 5 1919 5 30 7 10 20记录向量与地址向量相结合主

4、目录下一页上一页退出本章要点假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式下的数据类型可描述为：MAX01234key info#define MAX 20 typedef struct int key;int otherinfo;RecordType;typedef struct RecordType stMAX+1;int length;RecordList;0号元素为监视哨主目录下一页上一页退出本章要点排序方法插入类排序选择类排序交换类排序归并排序直接插入排序折半插入排序简单选择排序堆排序起泡排序多关键字排序分配类排序链式基数排序基数排序的顺序表结

5、构快速排序树形选择排序表插入排序希尔排序主目录下一页上一页退出本章要点直接插入排序n 基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。8.2 插入类排序主目录下一页上一页退出本章要点该算法适合于n 较小的情况，时间复杂度为O(n2).待排元素序列：53 27 36 15 69 42第一次排序：27 53 36 15 69 42第二次排序：27 36 53 15 69 42第三次排序：15 27 36 53 69 42第四次排序：15 27 36 53 69 42第五次排序：15 27 36 42 53 69 对于有n

6、个数据元素的待排序列，插入操作要进行n-1次8.2.1 直接插入排序主目录下一页上一页退出本章要点void insertSort(RedType L,int n)int i,j;for(i=2;i=n;i+)if(Li.keyLi-1.key)L0=Li;/*作为监视哨*/for(j=i-1;L0.keyLj.key;j)Lj+1=Lj;/*记录后移*/Lj+1=L0;/*插入*/8.2 插入类排序主目录下一页上一页退出本章要点n 平均时间复杂度：O(n2)n 稳定性：稳定的排序方法待排元素序列：53 27 36 15 69 36第一次排序：27 53 36 15 69 3

7、6第二次排序：27 36 53 15 69 36第三次排序：15 27 36 53 69 36第四次排序：15 27 36 53 69 36第五次排序：15 27 36 36 53 69 直接插入类排序分析主目录下一页上一页退出本章要点n 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。n 折半插入排序的条件：在有序序列中插入一个关键字8.2.2 折半插入排序主目录下一页上一页退出本章要点例：有6个记录，前5 个已排序的基础上，对第6个记录排序。15 27 36 53 69 42 low mid high 15

8、27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69(high36)(4253)折半插入排序过程主目录下一页上一页退出本章要点void BinsertSort(RedType L,int n)int i,low,high,mid;for(i=2;i=n;+i)L0=Li;/*r0作为监视哨*/low=1;high=i-1;While(low=high)mid=(low+high)/2;if(L0.key=high+1;j)Lj+1=Lj;/*记录后移*/Lhigh+1=L0;/*插入*/*fo

9、r*/*折半插入排序*/折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。/*折半后的位置*/主目录下一页上一页退出本章要点n 基本思想：先在待插入记录之前的有序子链表中查找应插入位置，然后将待插入记录插入链表8.2.3 表插入排序主目录下一页上一页退出本章要点n 基本思想：先将整个待排记录序列分割成若干序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序8.2.4 希尔排序主目录下一页上一页退出本章要点初始关键字序列：46 55 13 42 94 46 07 70第一趟排序结果：4

10、6 46 07 42 94 55 13 7046 94 46 55 07 13 42 70d1=413 42 46 46 70 94 07 55d2=3第二趟排序结果：13 46 07 42 70 55 46 94希尔排序过程主目录下一页上一页退出本章要点第三趟排序结果：07 42 13 46 46 55 70 9407 13 46 70 42 46 55 94d3=2d4=1第二趟排序结果：13 46 07 42 70 55 46 94第四趟排序结果：07 13 42 46 46 55 70 9407 13 42 46 46 55 70 94希尔排序是一种不稳定的排序方法希尔排序过

11、程主目录下一页上一页退出本章要点简单选择排序n 基本思想：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并与第i个记录交换n 特点：其比较次数与关键字的初始排列状态无关8.3 选择类排序主目录下一页上一页退出本章要点初态8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 ijki j ki j ki j k1 3 9 8 6 互换i jk1 3 9 8 6 ikj1 3 9 8 6 ikj第一趟第二趟1 3 9 8 6 i k j第三趟简单选择排序过程主目录下一页上一页退出本章要点void SelectSort(

12、RedType L,int n)int i,j,k,t;for(i=1,i=n;+i）/*选择第i小的元素，并交换到位*/k=i；for(j=i+1;j=n;+j)if(Lj.keyLk.key)k=j;/*Lk 中存放的是第I小的元素*/if(k!=i)t=Li;/*交换*/Li=Lk;Lk=t；/*FOR*/*SelectSort*/8.3.1 简单选择排序主目录下一页上一页退出本章要点n 平均时间复杂度：O(n2)n 稳定性：不稳定的排序方法例如：初始关键字序列：46 55 13 42 94 46 07 70第一趟排序结果：07 55 13 42 94 46 46 70第二趟排

13、序结果：07 13 55 42 94 46 46 70第三趟排序结果：07 13 42 55 94 46 46 70第四趟排序结果：07 13 42 55 46 94 46 70第五趟排序结果：07 13 42 55 46 46 94 70第六趟排序结果：07 13 42 55 46 46 70 94简单选择排序分析主目录下一页上一页退出本章要点n 基本思想：每一趟在n-i+1个记录中选出关键字最小的记录作为有序序列中第i个记录8.3.2 树形选择排序主目录下一页上一页退出本章要点初始关键字序列：46 55 13 42 94 46 07 7046 55 13 42 94 4

14、6 07 7046 13 46 0713 0707第一趟选择结果树形选择排序过程主目录下一页上一页退出本章要点初始关键字序列：46 55 13 42 94 46 07 7046 55 13 42 94 46 7046 13 46 7013 4613第二趟选择结果树形选择排序过程主目录下一页上一页退出本章要点初始关键字序列：46 55 13 42 94 46 07 7046 55 42 94 46 7046 42 46 7042 4642第三趟选择结果树形选择排序过程主目录下一页上一页退出本章要点初始关键字序列：46 55 13 42 94 46 07 7046 5

15、5 94 46 7046 46 7046 4646第四趟选择结果树形选择排序过程主目录下一页上一页退出本章要点n 堆排序：也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。n 堆的示例8.3.3 堆排序8976 243315 101125 3649 78 56(a):堆顶元素取最大值(b):堆顶元素取最小值主目录下一页上一页退出本章要点n 实现堆排序需解决两个问题：n 如何由一个无序序列建成一个堆？n 输出堆顶元素后，如何将剩余元素调整成一个新的堆？8.3.3 堆排序主目录下一页上一页

16、退出本章要点6525 3656 49 78 41(a)65 3656 49 78 41(b)252549 3656 65 78 41(c)把自堆顶至叶子的调整过程称为“筛选”。从一个无序序列建堆的过程就是一个反复”筛选“的过程。调整堆的过程主目录下一页上一页退出本章要点n 具体做法：把待排序的记录的关键字存放在数组r1.n之中，将r看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录r1作为二叉树的根，以下各记录r2.n依次逐层从左到右顺序排列。然后对这棵完全二叉树进行调整。建立堆的过程2556 4978 1 1 65 4136(a)无序序列n=8,int(n/2)

17、=4开始2556 4936 1 1 65 4178(b):78被筛选后的状态2556 4136 11 65 4978(c):49被筛选后的状态2511 4136 56 65 4978(d):56被筛选后的状态(e):被筛选之后建成小根堆1125 4136 56 65 4978初始关键字序列：25 56 49 78 11 65 41 36主目录下一页上一页退出本章要点2556 4978 11 65 4136(a)无序序列(b):被筛选之后建成大根堆7856 6536 11 49 4125初始关键字序列：25 56 49 78 11 65 41 36主目录下一页上一页退出本章要

18、点A:2556 4978 1 1 65 4136i=4(1)2556 49781 1 65 4136i=3(2)2556 65781 1 49 4136(3)(4)2556 65781 1 49 4136i=2(5)2578 65561 1 49 4136i=1堆排序主目录下一页上一页退出本章要点(7)2556 65361 1 49 4178B:(6)7856 6536 1 1 49 4125重新调整为一个堆(8)1125 364149 56 6578最终结果主目录下一页上一页退出本章要点n 交换排序的特点在于交换。n 有冒泡和快速排序两种。8.3 交换类排序主目录下一页

19、上一页退出本章要点冒泡排序（起泡排序）思想：小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上；依次类推，则完成排序。正序：时间复杂度为O(n)逆序：时间复杂度为O(n2)适合于数据较少的情况。排序n个记录的文件最多需要n-1趟冒泡排序。8.3.1 冒泡排序主目录下一页上一页退出本章要点第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始关键字思想：小的浮起，大的沉底。49 36 4

20、1 65 1178 3665 36 4156 36 41 6541 36 41 56 11 7836 36 41 49 11 56 4925 25 25 11 49 49 5611 11 11 25 25 25 25冒泡排序的过程主目录下一页上一页退出本章要点冒泡排序的C程序段：Void bubsort(RedType L,int n)chang=TRUE;for(i=1;i=n-1&change;i+)change=FALSE;for(j=1;j=n-i;j+)if(Lj.keyLj+1.key)x=Lj;Lj=Lj+1;Lj+1=x;change=TRUE;/*while*/*B

21、obsort*/8.3.1 冒泡排序主目录下一页上一页退出本章要点n 平均时间复杂度：O(n2)n 稳定性：稳定的排序方法例如：初始关键字序列：46 55 13 42 94 46 07 70第一趟排序结果：46 13 42 55 46 07 70 94第二趟排序结果：13 42 46 46 07 55 70 94第三趟排序结果：13 42 46 07 46 55 70 94第四趟排序结果：13 42 07 46 46 55 70 94第五趟排序结果：13 07 42 46 46 55 70 94第六趟排序结果：07 13 42 46 46 55 70 94冒泡排序的性能分析主目录下

22、一页上一页退出本章要点思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。关键字通常取第一个记录的值为基准值。做法：附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设关键字为 key，首先从 high所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换，然后从low 所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至low=high为止。8.3.2 快速排序主目录下一页上一页退出本章要点有序序列 6 18 23 52 67key初始序列 23 52 6

23、67 18low high一次交换 18 52 6 67 23 lowhigh二次交换 18 23 6 67 52high 三次交换 18 6 23 67 52/完成一趟排序后分别进行快速排序low high快速排序的过程主目录下一页上一页退出本章要点n 平均时间复杂度：O(log2n)n 稳定性：不稳定的排序方法初始关键字序列：48 62 35 77 55 14 35 98一次划分的结果：35 14 35 48 55 77 62 98二次划分的结果：14 35 35 48 55 77 62 98三次划分的结果：14 35 35 48 55 62 77 98 快速排序的性能分析主目录下一页上一页退出本章要点初始序列 23 52 67 6 18 10一趟归并后 23 52 6 67 10 18二趟归并后 6 23 52 67 10 18三趟归并后 6 10 18 23 52 67归并排序示例功能：将两个或两个以上的有序表组成一个新的有序表。思想：把具有n个记录的表看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到n/2个长度为2或为1的有序子表；再两两归并，如此重复，直到得到一个长度为n的有序表为止。8.5 归并排序

展开阅读全文