是一种效率较高的查找方法，但是只适合顺序存储 是一种效率较高的查找方法，但是只适合顺序存储 的有序表。 的有序表。 二分查找的方法： 二分查找的方法：首先将关键字与线性表中间位置 的结点比较，相等则查找成功；不相等则根据比较 的结点比较，相等则查找成功； 结果确定下一步查找应在哪个子表中进行； 结果确定下一步查找应在哪个子表中进行；重复上 述过程，直至查找成功或子表长度为0。 述过程，直至查找成功或子表长度为 。 二分查找法的适用场合： 二分查找法的适用场合： 线性表中的元素按关键字值递增或递减的次序排 列； 线性表采用顺序存储结构。 线性表采用顺序存储结构。 第58页
折半查找算法举例
对给定数列（有序） 3， 11，17，21，23，28， 对给定数列（有序）{ 3，5，11，17，21，23，28， 30，32，50}，按折半查找算法，查找关键字值为30 30，32，50}，按折半查找算法，查找关键字值为30 的数据元素。 的数据元素。
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 3， 11，17，21，23，28，30，32， 第1次： { 3，5，11，17，21，23，28，30，32，50 } K=30 mid1=（1+10） mid1=（1+10）/2 = 5 low mid high
k>a(mid1)=a(5)=21
23，28，30，32， 第2次： { 23，28，30，32，50 low
上一页 下一页 停止放映 } high mid
mid2 = （6+10） /2 = 8 6+10） K=a(mid2)=a(8)=30 第59|92页 59|92页 |92 练习
假设待查有序（升序）顺序表中数据元素的关键字序列 为（8,18,27,42,47,50,56,
21
68,95,120），用折半查找 方法查找关键字值为27的数据元素.
对于长度为n的有序线性表，最坏情况只需比较log2n次 对于长度为n的有序线性表，最坏情况只需比较log2n次。 log2n 第60页 ⒍ 排序技术
排序指将一个无序序列整理成按关键字值递增或递减排列的有序 排序指将一个无序序列整理成按关键字值递增或递减排列的有序 序列。 序列。 顺序存储的线性表 排序方法中其排序对象一般是顺序存储的线性表。 排序方法中其排序对象一般是顺序存储的线性表。 根据排序序列的规模以及数据处理的要求， 根据排序序列的规模以及数据处理的要求，可以采用不同的排序 方法： 交换类排序法 冒泡排序 快速排序 插入类排序法
简单插入排序 希尔排序 选择类排序法 简单选择排序 堆排序 第61页 冒泡排序
冒泡排序的方法： 冒泡排序的方法： 扫描整个线性表， 扫描整个线性表，逐次对相邻的两个元素进行比 若为逆序，则交换； 较，若为逆序，则交换；第一趟扫描的结果使最 或最小)的元素排到表的最后 或最前) 大(或最小 的元素排到表的最后 或最前 ； 或最小 的元素排到表的最后(或最前 除最后(或最前)一个元素 除最后(或最前)一个元素，对剩余的元素重复上 或最前 一个元素， 述过程，将次大(或次小 的数排到表的倒数(或正 或次小)的数排到表的倒数 述过程，将次大 或次小 的数排到表的倒数 或正 第二个位置； 数)第二个位置； 第二个位置 重复上述过程； 重复上述过程； 对于长度为n的线性表， 对于长度为 的线性表，冒泡排序需要对表扫描 的线性表 n-1遍。 遍 第62页 冒泡排序的方法
设待排数据元素的关键字为（ ， ， ， 设待排数据元素的关键字为（18，20，15， 32，4，25），第一趟冒泡排序后的序列状 ），第一趟 ， ， ），第一趟冒泡排序后的序列状 态
22
如图所示：
18 18 18 18 18 18 上一页 下一页 停止放映
20 15 32 4 20 15 32 4 15 20 32 4 15 20 32 4 15 20 4 32 15 20 4 25 25 25 25 25 25 32 最大数 第63|92页 63|92页 |92 第二趟冒泡排序
Q：第二趟冒泡排序后的结果是什么样的？达到 ：第二趟冒泡排序后的结果是什么样的？
了最终的排序目标吗？ 了最终的排序目标吗？一共需要多少次能够最 后成为有序序列？ 后成为有序序列？ Q：你觉得冒泡排序的效率如何？如果是你，你 ：你觉得冒泡排序的效率如何？如果是你， 会用什么方法来排序？ 会用什么方法来排序？ 冒泡排序比较简单，当初始序列基本有序时， 冒泡排序比较简单，当初始序列基本有序时， 冒泡排序有较高的效率，反之效率较低。 冒泡排序有较高的效率，反之效率较低。 冒泡排序终止条件: 冒泡排序终止条件
本趟排序未发生交换， 本趟排序未发生交换，终止排序算法 上一页 下一页 停止放映 第64|92页 64|92页 |92
设待排数据元素的关键字为 （26,18,32,54,47,9,15 )
初始 序列 第一趟 排序后 第二趟 排序后 第三趟 排序后 第四趟 排序后 第五趟 排序后
26 18 32 54 47 9 15 上一页 下一页 停止放映 18 26 32 47 9 15 54 18 26 32 9 15 47 18 26 9 15 32 18 9 15 26 9 15 18
冒泡排序法，需要比较的次数为n(n-1)/2； 冒泡排序法，需要比较的次数为n(n-1)/2； n(n
23
第65|92页 65|92页 |92 选择排序
选择排序的方法： 选择排序的方法： 扫描整个线性表，从中找出最小的元素， 扫描整个线性表，从中找出最小的元素，与第 一个元素交换； 一个元素交换； 除第一个元素，对剩下的子表采用相同的方法 除第一个元素， 找出次小的数，与第二个数交换； 找出次小的数，与第二个数交换； 重复上述过程； 重复上述过程； 对于长度为n的线性表， 对于长度为 的线性表，选择排序需要对表扫 的线性表 描n-1遍。 遍
简单选择排序法, 最坏情况需要n(n 1)/2次比较 n(n次比较； 简单选择排序法, 最坏情况需要n(n-1)/2次比较； 第66页
例：设待排数据元素的关键字为（15，14，22，30， 设待排数据元素的关键字为（ ， ， ， ， 37，11），每一趟排序后的序列状态如图所示： ），每一趟排序后的序列状态如图所示 ， ），每一趟排序后的序列状态如图所示： 初态： 初态：
[15，14，22，30，37，15，11] ， ， ， ， ， ，
第一趟： 第一趟： [11] [14，22，30，37，15，15] ， ， ， ， ， 第二趟： 第二趟： [11，14] [22，30，37，15，15] ， ， ， ， ， 第三趟： [11，14， [30，37，22， 第三趟： [11，14，15] [30，37，22，15] 第四趟： [11，14，15，15] [37，22，30] 第四趟： ， ， ， ， ， 第五趟： 第五趟： [11，14，15，15，22] [37，30] ， ， ， ， ， 上一页 下一页 停止放映
第六趟： 第六趟： [11，14，15，15，22，30] [37] ， ， ， ， ， 有序序列 第67|92页 67|92页 |92 排序法小结： 排序法小结：
简单选择排序法, 最坏情况需要n(n-1)/2次比较； 次比较； 简单选择排序法 最坏情况需要 次比较 冒泡排序法, 冒泡排序法 希尔排序法, 希尔排序法 堆排序法, 堆排序法 最坏情况需要n(n-1)/2次比较； 次比较； 最坏情况需要 次比较 最坏情况需要O(n1.5)次比较； 次比较； 最坏情况需要 次比较 最坏情况需要O(nlog2n)次比较； 次比较； 最坏情况需要 次比较 第68页
排序查找方面的考题： 排序查找方面的考题：
24
(1) 对于长度为 的线性表，在最坏情况下，下列各排序法所对应的比较 对于长度为n的线性表，在最坏情况下， 的线性表 次数中正确的是（ 次数中正确的是（2005年4月） 年 月 D A) 冒泡排序为 冒泡排序为n/2 B) 冒泡排序为 冒泡排序为n C) 快速排序为 快速排序为n D) 快速排序为 快速排序为n(n-1)/2 (2)在长为 的有序线性表中进行顺序查找，最坏情况下需要比较的次数 在长为64的有序线性表中进行顺序查找 在长为 的有序线性表中进行顺序查找， 为。（06年9月） 。 年 月 A）、 ）、63 ）、 B）、 ）、64 ）、 C）、 ）、6 ）、 D）、 ）、7 ）、 B
(3) 下列数据结构中，能用二分法进行查找的是（2005年9月） 下列数据结构中，能用二分法进行查找的是（ 年 月 A）顺序存储的有序线性表 B）线性链表 ） ） A C）二叉链表 D）有序线性链表 ） ） (4) 下列排序方法中，最坏情况下比较次数最少的是（09年3月） 下列排序方法中，最坏情况下比较次数最少的是（ 年 月 A）冒泡排序 B）简单选择排序 ） ） D C）直接插入排序 ） D）堆排序 ） 第69页
第二章 程序设计基础
内容： 内容：? 1. 程序设计方法与风格。 程序设计方法与风格。 结构化程序设计。 ?2. 结构化程序设计。 面向对象的程序设计方法，对象， ?3. 面向对象的程序设计方法，对象，方 属性及继承与多态性。 法，属性及继承与多态性。 第70页
1．结构化程序设计
结构化程序设计方法的四条原则是：
1. 2. 3. 4. 自顶向下； 逐步求精； 模块化； 限制使用goto语句。 结构化程序的基本结构和特点： 结构化程序的基本结构和特点：
（1）顺序结构： ）顺序结构： 简单的程序设计，最基本、最常用的结构； （2）选择结构（分支结构）： ）选择结构（分支结构）： 包括简单选择和多分支选择结构， （3）重复结构（循环结构）： ）重复结构（循环结构）： 可根据给定条件，判断是否需要重复执行某一相同程序段。 第71页
2．面向对象的程序设计
对象是面向对象方法中最基本的概念。 对象是面向对象方法中最基本的概念。
25