首页计算机计算机基础数据结构 08 排序.pptx

08 排序.pptx

页数:36页文件大小:594.8 KB来源: 数据结构ppt课件

本课件为数据结构第八章排序,先说明排序的定义与稳定性,随后依次讲解直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序与基数排序的算法思想与实现,并对各类排序方法的时间复杂度与适用场景作比较分析。

第八章排序目录页,列出插入排序、交换排序、选择排序与排序方法比较等小节
排序定义与分类页,给出内部排序、外部排序及插入交换选择三类排序依据
排序分类页,说明按工作量分为简单与先进排序方法,并给出稳定性判定示例
查看本课件的文字版(共 36 页,供检索与复制)

第1页:第八章排序目录

排序插入排序交换排序选择排序本章小结第八章排序排序方法比较

第2页:排序的定义与分类

排序定义——将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列叫~ 排序分类 按待排序记录所在位置 内部排序:待排序记录存放在内存 外部排序:排序过程中需对外存进行访问的排序 按排序依据原则 插入排序:直接插入排序、折半插入排序 交换排序:冒泡排序 选择排序:简单选择排序、堆排序排序Sorting每次将一个待排序的记录,按关键字的大小插入到已排好序的子序列中的适当位置,直到全部记录插入完毕为止两两比较待排序记录的关键值,交换不满足顺序要求的记录,直到全部满足顺序要求为止每次从待排序记录中选出关键字最小的记录,顺序放在已排序的记录序列的后面,直到全部排完为止

第3页:排序的工作量分类

按排序所需工作量 简单的排序方法:T(n)=O(n²) 先进的排序方法:T(n)=O(nlog2n) 排序基本操作 比较两个关键字大小 将记录从一个位置移动到另一个位置 排序算法稳定性排序Sorting待排序数列中如果有关键字相等的记录,例如:654938 63 974913 27 55 04经某一种算法排序时,0413 27 38494955 63 65 97关键字相等的记录其先后次序始终不变,则称排序算法为稳定的,具有稳定性;否则不稳定,具有不稳定性

第4页:待排序记录的数据类型

待排序记录的数据类型# define MaxSize 20//顺序表长度typedefint KeyType;//定义关键字类型为整型

typedefstruct{ KeyType key;//主关键字……//其他数据项}RedType;待排序记录结构顺序表结构typedefstruct{ RedType r[MaxSize+1];//r[0]为“监视哨”int length;//顺序表长度}SqList;排序Sorting

第5页:插入排序的基本思想

插入排序的基本思想:每次将一个待排序的记录,按关键字的大小插入到已排好序的子序列中的适当位置,直到全部记录插入完毕为止。插入排序InsertionSorting

第6页:直接插入排序过程

排序过程: 先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序; 整个排序过程为n-1趟插入。直接插入排序Straight InsertionSort

第7页:直接插入排序示例

待排序记录为R[i],将其与R[j](j=i-1)进行比较—— 若R[i]>R[j]——R[i]位置不变 若R[i]<R[j]——

  • 将R[i]放在“监视哨”的位置;
  • R[j]后移,j--,直到R[i]≧R[j];
  • 将R[0]放置于R[j+1]的位置直接插入排序Straight InsertionSort初始0 1 2 3 4 513268513*0 1 2 3 4 513第一趟j30300 1 2 3 4 513第二趟30j26j0 1 2 3 4 513第三趟3026j850 1 2 3 4 513第四趟30268513*jjjj稳定的排序方法

第8页:直接插入排序存储结构

直接插入排序Straight InsertionSort 算法描述

typedefstruct{ ElemType r[MAXSIZE+1];// r[0]为监视哨int length;//表的长度}SqList;表的顺序存储结构typedefstruct{ KeyType key;//关键字域……//其它域}ElemType;数据元素类型

第9页:直接插入排序算法

直接插入排序Straight InsertionSort 算法描述

void InsertSort( SqList &L){int i, j;for(i=2; i<=L.length; i++){if(L.r[i].key<L.r[i-1].key){ L.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];}}}从第2个记录开始排序与有序序列的最后一个记录比较若待排序记录较小,则元素后移将待排序记录放置r[j+1]的位置

第10页:直接插入排序性能分析

算法评价 时间复杂度 若待排序记录按关键字从小到大排列(正序) 关键字比较次数: 记录移动次数: 若待排序记录按关键字从大到小排列(逆序) 关键字比较次数: 记录移动次数: 若待排序记录是随机的,取平均值 关键字比较次数: 记录移动次数: 空间复杂度:直接插入排序Straight InsertionSort01231344949*5152123456782805249*49343128121234567851T(n)=O(n2)S (n)=O(1)

第11页:折半插入排序过程

排序过程:用折半查找方法确定插入位置的排序折半插入排序Binary InsertionSort初始0 1 2 3 4 530 13268515i=20 1 2 3 4 51330i=50 1 2 3 4 5301326lowhighmid 待排序记录为R[i] low=1,high=i-1,mid=(low+high)/2 将R[i]与R[mid]比较,进行折半查找,直到low>high……1585

第12页:折半插入排序示例

排序过程:用折半查找方法确定插入位置的排序折半插入排序Binary InsertionSort初始0 1 2 3 4 530 13268515i=20 1 2 3 4 51330i=50 1 2 3 4 5301326lowhigh 待排序记录为R[i] low=1,high=i-1,mid=(low+high)/2 将R[i]与R[mid]比较,进行折半查找,直到low>high……1585 将i之前low之后元素后移 将R[0]插入到low所指示位置

第13页:折半插入排序算法

算法描述 算法评价折半插入排序Binary InsertionSort

void BinSort( SqList &L){ int i, j, high, low, mid;for(i=2; i<=L.length; i++){L.r[0]=L.r[i];low=1; high=i-1;while(low<=high){mid=(low+high)/2;if(L.r[0].key<L.r[mid].key)high=mid-1;else low=mid+1; }for(j=i-1; j>=low; j--)L.r[j+1]=L.r[j];L.r[low]=L.r[0];}}设置监视哨折半查找记录后移插入插入第i个记录折半插入排序与直接插入排序仅查找插入位置方法不同,记录移动次数不变T(n)=O(n2)S (n)=O(1)

第14页:交换排序的基本思想

交换排序的基本思想:两两比较待排序记录的关键值,交换不满足顺序要求的记录,直到全部满足顺序要求为止。交换排序ExchangeSorting

第15页:起泡排序过程

排序过程 将第一个记录与第二个记录的关键字进行比较,若为逆序则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止。第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作”为止起泡排序BubbleSort

第16页:起泡排序示例

132518713*初始起泡排序BubbleSort132518713*第一趟初始132518713*第二趟132518713*第三趟稳定的排序方法

  • 起泡排序最多执行几趟?
  • 第i趟排序需要比较几次?
  • 最多执行n-1趟
  • 第i趟排序需要比较n-i次结束

第17页:起泡排序算法

void BubbleSort( SqList &L){ int m, i, j,flag=1;m=L.length-1;while((m>0)&&(flag= =1)){flag=0;for(j=1;j<=m;j++)if(L.r[j].key>L.r[j+1].key){flag=1;L.r[0]=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=L.r[0];}m--;}}最多进行m趟排序m次比较上一趟排序有无交换操作,1(有)0(无)若相邻的两个元素逆序,则交换排序趟数-1(下一次比较次数-1)起泡排序BubbleSort

第18页:起泡排序性能分析

算法评价 时间复杂度 最好情况(正序) 比较次数: 移动次数: 最坏情况(逆序) 比较次数: 移动次数: 空间复杂度: 适用于元素较少,或初始序列基本有序起泡排序BubbleSortn-10T(n)=O(n2)132518713*132518716S(n)=O(1)

第19页:选择排序的基本思想

选择排序的基本思想:每次从待排序记录中选出关键字最小的记录,顺序放在已排序的记录序列的后面,直到全部排完为止。选择排序SelectionSorting

第20页:简单选择排序过程

简单选择排序(直接选择排序) 排序过程 首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换 再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换 重复上述操作,共进行n-1趟排序后,排序结束选择排序SelectionSorting

第21页:简单选择排序示例

132518713*第一趟132518713*第二趟13251813*7第三趟13251813*7第四趟132518713*初始简单选择排序SimpleSelectionSort不稳定的排序方法简单选择排序需要执行几趟?执行n-1趟结束

第22页:简单选择排序算法

算法描述

void SelectSort( SqList &L){ int i, j, k;for(i=1;i<L.length;i++){k=i;for(j=i+1;j<=L.length;j++)if(L.r[j].key<L.r[k].key)k=j;if(i!=k){L.r[0].key=L.r[i];L.r[i]=r[k];L.r[k]=L.r[0].key;}}}最小记录的下标每趟排序最小记录初始值第i趟排序——找到的最小记录应放在下标为i的位置查找最小记录最小记录不在“适当”位置上交换简单选择排序SimpleSelectionSort

第23页:简单选择排序性能分析

算法评价 时间复杂度 记录移动次数 最好情况: 最坏情况: 比较次数: 空间复杂度:简单选择排序SimpleSelectionSortT(n)=O(n2)03(n-1)每次找到的最小记录都在“适当”位置上每次找到的最小记录都不在“适当”位置上S(n)=O(1)

第24页:堆的定义

堆排序HeapSort 堆定义:n个元素的序列(k1,k2,……kn),当且仅当满足下列关系时,称之为堆ki k2iki k2i+1或(i=1,2,…... n/2 )ki k2iki k2i+1例(96,83,27,38,11,9)例(13,38,27,50,76,65,49,97)968327381191338509727497665可将堆序列看成完全二叉树,则堆顶元素(完全二叉树的根)必为序列中n个元素的最小值或最大值大顶堆(max heap)小顶堆(min heap)

第25页:堆排序的基本思路

堆排序:将无序序列建成一个堆,得到关键字最小(或最大)的记录;输出堆顶的最小(大)值后,使剩余的n-1个元素重又建成一个堆,则可得到n个元素的次小值;重复执行,得到一个有序序列,这个过程叫~ 堆排序需解决的两个问题: 如何由一个无序序列建成一个堆? 如何在输出堆顶元素之后,调整剩余元素,使之成为一个新的堆? 第二个问题解决方法——筛选 方法:输出堆顶元素(根)之后,以堆中最后一个元素替代之;然后将根结点值与左、右子树的根结点值进行比较,并与其中小(大)者进行交换;重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为“筛选”堆排序HeapSort

第26页:堆排序筛选过程一

例如,已知小顶堆,通过筛选,重新调整成小顶堆堆排序HeapSort1327384965765097123456781338275076654997①取得堆顶元素值用最后一个元素代替堆顶元素

第27页:堆排序筛选过程二

例如,已知小顶堆,通过筛选,重新调整成小顶堆堆排序HeapSort13273849657650971397972797499727123456781338275076654997

  • 将剩余元素调整成一个新的小顶堆
  • 取得堆顶元素值用最后一个元素代替堆顶元素

第28页:堆排序筛选过程三

堆排序HeapSort974938496576509713273897975038654965497650769750659797657697977697例如,已知小顶堆,通过筛选,重新调整成小顶堆123456781338275076654997

  • 将剩余元素调整成一个新的小顶堆
  • 取得堆顶元素值用最后一个元素代替堆顶元素利用小顶堆得到的是降序序列不稳定的排序方法

第29页:堆排序筛选结束

堆排序HeapSort974938496576509713273897975038654965497650769750659797657697977697例如,已知小顶堆,通过筛选,重新调整成小顶堆12345678133827507665499727973897496550766597769797利用小顶堆得到的是降序序列

  • 将剩余元素调整成一个新的小顶堆
  • 取得堆顶元素值用最后一个元素代替堆顶元素结束利用小顶堆得到的是降序序列

第30页:初建堆的方法

第一个问题(初建堆)解决方法 方法:从无序序列的第 n/2 个元素(即此无序序列对应的完全二叉树的最后一个非叶子结点)起,至第一个元素止,进行反复筛选完全二叉树:123114589126710堆排序HeapSort

第31页:初建堆示例

堆排序HeapSort通过反复筛选初建成小顶堆49653827137697505097136513494927初建堆结束493865977613275012345678例如,对无序序列 堆排序的优点:即使在最坏情况下,其时间复杂度也为O(nlog2n);只需一个辅助空间 记录数较少的序列,堆排序的优越性并不明显,但对大量的记录来说堆排序是很有效的

第32页:排序方法比较

稳定性辅助空间最坏时间平均时间排序方法稳定直接插入不稳定简单选择稳定冒泡排序不稳定堆排序排序方法比较选择排序方法考虑因素: 记录个数n 记录大小 记录键值分布 稳定性要求 辅助存储空间大小(1)n较小时,可采用简单排序方法(直接插入、直接选择和冒泡排序)(2)n较大时,应采用堆排序。(3)若待排序记录已基本有序时,应采用起泡排序(4)多种排序方法可结合使用

第33页:第八章本章小结

掌握排序的基本概念和性能分析方法,排序策略本章小结End掌握直接插入排序、折半插入排序算法及性能分析掌握起泡排序、简单选择排序算法及性能分析掌握堆排序的基本过程各种内部排序算法的比较

第34页:归并排序

归并——将两个或两个以上的有序表组合成一个新的有序表,叫~ 2-路归并排序 排序过程 设初始序列含有n个记录,则可看成n个有序的子序列,每个子序列长度为1 两两合并,得到 n/2 个长度为2或1的有序子序列 再两两合并,……如此重复,直至得到一个长度为n的有序序列为止归并排序Merge Sort

第35页:二路归并排序示例

4938 13 97 76 13*27 503849139713*762750第一趟1338499713*275076第二趟ji13归并排序Merge Sort第三趟i13*j27ji3849i50j76j97 稳定性:稳定的排序方法i

第36页:排序方法的选择

排序方法比较选择排序方法考虑因素: 记录个数n 记录大小 记录键值分布 稳定性要求 辅助存储空间大小稳定性辅助空间最坏时间平均时间排序方法直接插入简单选择冒泡排序堆排序归并排序稳定不稳定稳定不稳定稳定(1)n较小时,可采用简单排序方法(直接插入、直接选择和冒泡排序);(2)n较大时,应采用堆排序。要求稳定性时,可采用归并排序;(3)若待排序记录已基本有序时,应采用冒泡排序;(4)多种排序方法可结合使用。

顶部目录