首页计算机计算机基础程序设计基础与数据结构 10 第九章 排序.pptx

10 第九章 排序.pptx

页数:16页文件大小:122.3 KB来源: 程序设计基础与数据结构ppt课件

本课件系统讲解排序运算:先给出排序的定义并区分内部排序与外部排序,指出前四类内部排序基于关键字比较而基数排序基于分布规律;随后逐一讲解简单选择排序与堆排序、直接插入排序、二分插入排序与希尔排序、冒泡排序与快速排序,再介绍归并排序与基数排序,最后给出外部排序中直接归并排序法的两个步骤。

第九章章节目录页,列出排序的基本概念与选择、插入、交换、归并、基数及外部排序七节
排序基本概念页,给出排序定义并区分内部排序与外部排序及五类基本排序方法
选择排序导览页,说明每趟选出关键字最小元素放到已排序序列末端并列出两种实现
查看本课件的文字版(共 16 页,供检索与复制)

第1页:第九章 排序

第九章 排序

  • 排序的基本概念
  • 9.1 选择排序
  • 9.2 插入排序
  • 9.3 交换排序
  • 9.4 归并排序
  • 9.5 基数排序
  • 9.6 外部排序
  • 9.7 小结

第2页:排序的基本概念

排序的基本概念

  • 排序是把一组无序的数据按照关键字的某种次序排列成为一个有序序列的过程。
  • 排序过程中数据元素全部存放在内存中,称为内部排序;数据元素要在内外存之间移动的,称为外部排序。
  • 基本排序方法可分为五类:选择排序、插入排序、交换排序、归并排序和基数排序。
  • 前四种都是基于比较的排序方法,即通过比较关键字大小决定先后次序;基数排序不基于比较,而是基于数据元素的分布规律。

第3页:选择排序

9.1 选择排序:每次从待排序序列中选出关键字值最小(或最大)的元素,把它放到已排序序列的末端,反复进行直到序列中所有元素都排列完为止。

  • 简单选择排序
  • 堆排序

第4页:简单选择排序

9.1.1 简单选择排序:从所有待排序元素序列中选出关键字值最小的数据元素,将其与原序列中的第一个数据元素交换;然后在剩余元素序列中再选取关键字值最小的元素,与第二个元素交换;依此类推,即每一次都是在 n-i+1 个数据元素中选出关键字值最小的元素,将其与第 i 个数据元素交换。

第5页:堆排序

9.1.2 堆排序:堆排序是对简单选择排序的改进。

  • 堆是一棵完全二叉树,每个结点对应一个数据元素,且每个结点的值都不大于(或不小于)其孩子结点的值;堆的根结点具有最小(最大)值,堆的任一棵子树也是堆。
  • 基本思想:首先将待排序序列构造成堆,此时根结点具有最小(最大)值;然后输出根结点(堆顶),即成为已排序序列的第一个元素。
  • 再把剩余的 n-1 个结点构成的完全二叉树重新构造成堆,输出其根结点作为第二个元素;如此反复直到待排序序列为空,得到有序序列。

第6页:插入排序

9.2 插入排序:每一次排序都是将一个待排序的数据元素按其关键字值的大小插入到已排序序列的适当位置上,使之保持有序。

  • 直接插入排序
  • 二分插入排序
  • 希尔排序

第7页:直接插入排序

9.2.1 直接插入排序:将待排序元素插入到已排序序列时,插入位置是采用顺序查找的方法得到的。直接插入排序算法简单,常用于数据量较少或待排序序列基本有序的情况,但当数据量较大时效率不高。

第8页:二分插入排序

9.2.2 二分插入排序:待排序元素的插入位置是采用二分查找的方法得到的,能比直接插入排序的顺序查找更快地确定插入位置。

第9页:希尔排序

9.2.3 希尔排序:希尔(Shell)排序又称缩小增量排序。

  • 将整个待排序序列按下标的增量分为若干子序列,对每个子序列分别进行直接插入排序;随着增量减小,子序列包含的元素越来越多,整个序列逐步有序,最后增量为 1,对包含全部元素的序列进行一次直接插入排序。
  • 由于相隔某个下标增量的元素才组成一个子序列,数据元素的移动是跳跃式的,从而提高了排序效率。

第10页:交换排序

9.3 交换排序:基本思想是比较两个相邻数据元素的关键字值,将不满足次序要求的数据元素交换位置,直到所有数据元素都满足次序要求为止。

  • 冒泡排序
  • 快速排序

第11页:冒泡排序

9.3.1 冒泡排序:以递增序排序为例,在每一趟排序中先比较第一个与第二个元素的关键字,若逆序则交换,接着比较第二个与第三个,如此反复直到最后两个元素,关键字值最大的元素被交换到序列尾端;再对剩余序列作相同操作,使次大元素到达倒数第二的位置,依此类推,直到某趟不出现交换或只剩一个元素为止。

  • 关键字值最大的元素下沉(最小的元素上浮),如同冒泡一般,因此而得名。
  • 效率与待排序序列的初始状态有关:基本有序时比较与交换次数少、效率较高;基本逆序时次数多、效率较低。
  • 由于只对相邻元素比较交换,元素移动幅度较小,限制了冒泡排序的效率。

第12页:快速排序

9.3.2 快速排序:快速排序由冒泡排序改进而来,是内部排序众多算法中速度最快的一种。

  • 在一次排序中,从待排序数据元素中任取一个作为基准(支点),将其排在其最终位置上。
  • 同时把所有数据元素划分为两部分:第一部分各元素的关键字值都小于等于基准元素,第二部分各元素的关键字值都大于基准元素。
  • 依此类推,对分成的两个子序列重复排序,直到所有元素都被放在正确位置上为止。

第13页:归并排序

9.4 归并排序:归并排序是将两个或两个以上的有序序列合并成一个新的有序序列的过程。

  • 把 n 个元素的待排序序列看作 n 个长度为 1 的有序表,在此基础上进行有序表的合并。
  • 首先将这 n 个有序表从左至右两两合并,得到 ⌊n/2⌋ 个长度为 2 的有序表;再对它们两两合并,如此重复。
  • 每一次合并都使排序子表数量减少一半、长度增倍,最后只剩下一个长度为 n 的有序表,排序完成。

第14页:基数排序

9.5 基数排序:基数排序(Radix Sort)的排序过程通过分配和收集完成,又称为桶排序(Bucket Sort)或箱排序(Bin Sort)。

  • 文件中第 i 个元素的关键字 Ki 由 d 个分量组成,每个分量都是一个独立关键字,取值范围可能不同。
  • 基数排序根据多关键字排序,含 d 个关键字的文件需进行 d 趟排序;第 j 趟按关键字第 j 个分量排序。
  • 设置若干个箱子(个数由分量的取值范围即基 r 决定),依次扫描待排序元素,把关键字分量等于 k 的记录装入第 k 个箱子(分配),再按序号依次把各非空箱子收集起来;从低位到高位共进行 d 趟,所得序列即为有序排列。

第15页:外部排序

9.6 外部排序:当待排序数据量太多或记录数量太大、无法一次装入内存时,需依赖外部存储装置,通过内外存之间的数据交换来排序,这时使用的是外部排序法。

  • 直接归并排序法是最常用的外部排序法,可分为两个相对独立的步骤。
  • 第一步:将待排序文件分为几个可载入内存的子文件或段,用内部排序法将各段内记录排序,并把排序后得到的有序子文件重新写入外存,这些有序子文件称为归并段或顺串。
  • 第二步:对这些归并段进行两两合并,使归并段由小至大,当所有归并段合并成一个段后即得到有序文件,排序完成。

第16页:第九章小结

9.7 小结

  • 五种常用的内部排序方法及其算法实现:选择排序、插入排序、交换排序、归并排序、基数排序。
  • 各算法适用于具有不同初始状态的排序:待排序元素数量较少时往往采用较简单的算法,如直接插入排序、简单选择排序、冒泡排序;数据量较多时往往采用堆排序、快速排序、归并排序等。
  • 简单介绍外部排序方法。
顶部目录