2019/4/3 计算机基础 16
比较次数
1
2019/4/3
2
4
8
22
15
计算机基础
选择排序小结
N个数据元素的顺序表 第几趟 互换次数 选择排序：是完成数据一项项互换到对应 1 N-1 0 或1 内存位置中的过程，每一趟循环中嵌有一 2 N-2 0 或1 个比较循环结构，互换分支结构。 3 N-3 0或1 … … 0 或1 其每趟比较次数确定，互换次数不确定， … … 0 或1 趟数确定。 1 N-1 0 或1 共N-1趟 总计多少次？ 最多？最少？
1. 从N个元素里选择最小值，交换到第一个位 置，也就是排头1号位置。 2. 剩下N-1个元素里选择最小值，交换到第二个 位置，2号位置。 3. 剩下N-2个元素选择最小值，交换到3号位置。 …… N-1. 当排1,2,3……n-1都排好，剩下一个位置 肯定是排尾。
2019/4/3 计算机基础 14
要交换顺序表里两个元素的位置，则必 须使用一个“过渡内存”。
在控制器的控制下，经过内存的多次读 写操作，完成了内存中数据互换。
2019/4/3 计算机基础 6
任务二
内存中有一个顺序表，有两个数据元素， 要求小数在1号位，大数在2号位。

2019/4/3
计算机基础
7
任务二：按序交换是一个分支结构
计算机基础
12
任务五：循环任务四 长度为4的序列，要找几次最小值放置于
对于位置？长度为N呢？ 长度4，确定3个位置. 长度N，确定N-1个位置。 每次找到最小值并交换到对应位置： 我们称其为一趟 长度为N的序列排序趟数也是一个循环 结构，界值条件为N-1
2019/4/3 计算机基础
13
选择排序原理 长度为N的顺序表

在控制器控制下，从内存中取出X，Y放 入运算器比较大小，假如X小，那么正好 满足要求；假如Y小，那么要交换位置。
这是一个分支结构，需要一个判断条件： 小值是否正好在1号位置。
2019/4/3
计算机基础
8
三个元素的顺序表，找出其最小值，并 将其写入一个过渡内存。 运算器每次只能比较两个数
任务三
4 8 1 12 33 25 67 16 44 87 1 4 8 12 16 25 33 44 67 87 请排序：Excel
2019/4/3
计算机基础
3
利用计算机实现排序的方法。
2019/4/3
计算机基础
4
任务一
2019/4/3
计算机基础
5
任务一:数据交换
顺序表，有两个数据元素，占用了地址 编号为1,2的两个连续内存空间。
2019/4/3
计算机基础
1
复习提问
数据结构的两种结构，每种结构有哪些例 子
逻辑结构
线性结构：线性表，栈，队列，数组，串。 非线性结构：树，二叉树，图。
存储结构：顺序存储结构和链式存储结构
查找算法有哪两种
顺序查找法和二分法(序列前提条件是什么)
2019/4/3 计算机基础 2
二分法要求序列必须是有序序列，那么 我们怎么把一个无序顺序存储的线性结 构序列排好序呢 请排序（默认升序）
原序列：5个元素。写出每趟结果，交换次数，比较次数。
1
2
8
4
22
第一趟：比较4次，交换0次。结果：第一个元素固定。
1
2
8
4
22
第二趟：比较3次，交换0次。结果：前两个元素固定
1
2
8
4
22
第三趟：比较2次，交换1次。结果：前三个元素固定
1ห้องสมุดไป่ตู้
2
4
8
22
第四趟：比较1次，交换0次。结果：前四个元素固定 完成
2019/4/3
计算机基础
9
任务三：找最小值是一个循环结构
X和Y先比较，得到较小值；再把这个较
2019/4/3
小值和Z比较，得到的较小数就是最小值。 3 个数比较 2 次得到最小值。 6 5 11 2 4 个数比较 次得到最小值。 N个数比较 次得到最小值。 从长度为N的序列中找最小值，是一个 循环比较的过程，退出循环的界值条件 N-1。
计算机基础 10
：把任务三中，三个数中的最小值与内 存1号位互换（利用过渡内存）。
任务四
任务二我们已经知道，数据交换是一个分 支结构。
2019/4/3
计算机基础
11
任务五：循环任务四 从任务四中剩下的 2号3号位再找出最小
值，与2号位互换。
2019/4/3
至此，1号放置的是最小值，2号放置的 是中间值，那么3号呢？是不是已经完成 了从小到大排序？