数据结构-用面向对象语言描述-殷人昆-第九章

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

第九章 排序

主讲：杨同峰1

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

第九章 排序

概述插入排序

交换排序选择排序 基数排序

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

概述

排序：将一组杂乱 无章的数据按一定 的规律顺次排列起 来。3

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

概述

排序码(key): 通常数据元素有 多个属性域, 即多个数据成员组 成, 其中有一个属性域可用来区 分元素, 作为排序依据。该域即 为排序码。每个数据表用哪个 属性域作为排序码，要视具体 的应用需要而定。4

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

排序算法的稳定性: 如果在元素 序列中有 2 个元素r[i]和r[j], 它 们的排序码 k[i] == k[j] , 且在排 序之前, 元素r[i]排在r[j]前面。 如果在排序之后 , 元素 r [ i ] 仍在 元素r[j]的前面, 则称这个排序 方法是稳定的, 否则称这个排序 方法是不稳定的。5

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

内排序: 是指在 排序期间数据元 素全部存放在内 存的排序。6

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

外排序: 是指在排序期 间全部元素个数太多， 不能同时存放在内存， 必须根据排序过程的要 求，不断在内、外存之 间移动的排序。7

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

排序的时间开销: 排序 的时间开销是衡量算法好 坏的最重要的标志。排序 的时间开销可用算法执行 中的数据比较次数与数据 移动次数来衡量。8

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

算法运行时间代价的大略估 算 一般都按平均情况进 行估算。对于那些受元素排序码序列 初始排列及元素个数影响较 大的，需要按最好情况和最 坏情况进行估算。9

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

起泡排序 (Bubble Sort)

基本方法是：设待排序元素序列中的元素 个数为 n。最多作 n-1 趟，i = 1, 2, , n-1。 在第 i 趟中从后向前，j = n-1, n-2, , i, 顺次两两比较V[j-1].key和V[j].key。如果 发生逆序，则交换V[j-1]和V[j]。10

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

21 0

25 1

49 2 25

25* 3

164 25*

08 5

i=108

21

49

16

Exchang=1

i=208

16

21

25

49

25*

Exchang=1 2125 25*

i=308

16

49 Exchang=111

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

i=408 0

16 1

21 2

253

25*4

49 5 Exchang=0

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

算法分析 第 i 趟 对 待 排 序 元 素 序 列 V [ i 1],V[i], ,V[right]进行排序，结果将该序 列中排序码最小的元素交换到序列的第 一个位置(i-1)。 起泡排序需要一个附加元素以实现元素 值的对换。起泡排序是一个稳定的排序 方法。13

数据结构课件-本课件为我在大学教学过程中自行设计的课件,教材为 殷人昆 清华大学出版社 《数据结构-用面向对象语言描述》,欢迎各位同仁,各位同学下载。

最多做n-1趟起泡就能把所有元素排好序。 在元素的初始排列已经按排序码从小到大排好 序时，此算法只执行一趟起泡，做 n -1 次排序 码比较，不移动元素。这是最好的情形。 最坏的情形是算法执行 n - 1 趟起泡 , 第 i 趟 (1 ≤ i n) 做n-i次排序 …… 此处隐藏：753字，全部文档内容请下载后查看。喜欢就下载吧 ……