选择排序配套浙教版.ppt

西安电子科技大学计算机学院 - School of Computer Science Engineering, Xidian University, China * 简单选择排序 选择排序方法 1 2 3 4 5 6 7 43 18 9 13 55 7 43 以7个元素为例说明选择排序 位置1~位置7的元素初始排列如下所示 选择排序方法 1 2 3 4 5 6 7 43 18 9 13 55 7 43 第一趟：从7个元素中选出最小者，将其换入位置1，过程为：min为最小元素的位置序号（初值为1），令a(min)表示最小元素的值（初值为位置1的元素），逐一比较，找出最小元素及其位置 位置6的元素最小 交换 1 2 3 4 5 6 7 7 43 9 13 55 43 43 选择排序方法 1 2 3 4 5 6 7 7 18 9 13 55 43 43 第二趟：从6个元素中选出最小者，将其换入位置2，过程为：min为最小元素的位置序号（初值为2），令a(min)表示最小元素的值（初值为位置2的元素），逐一比较，找出最小元素及其位置 位置3的元素最小 交换 1 2 3 4 5 6 7 7 9 18 13 55 43 43 选择排序方法 1 2 3 4 5 6 7 7 9 18 13 55 43 43 第三趟：从5个元素中选出最小者，将其换入位置3，过程为：min为最小元素的位置序号（初值为3），令a(min)表示最小元素的值（初值为位置3的元素），逐一比较，找出最小元素及其位置 位置4的元素最小 交换 1 2 3 4 5 6 7 7 9 13 18 55 43 43 选择排序方法 1 2 3 4 5 6 7 7 9 13 18 55 43 43 第四趟：从4个元素中选出最小者，将其换入位置4，过程为：min为最小元素的位置序号（初值为4），令a(min)表示最小元素的值（初值为位置4的元素），逐一比较，找出最小元素及其位置 位置4的元素最小 交换 1 2 3 4 5 6 7 7 9 13 18 55 43 43 选择排序方法 1 2 3 4 5 6 7 7 9 13 18 55 43 43 第五趟：从3个元素中选出最小者，将其换入位置5，过程为：min为最小元素的位置序号（初值为5），令a(min)表示最小元素的值（初值为位置5的元素），逐一比较，找出最小元素及其位置 位置6的元素最小 交换 1 2 3 4 5 6 7 7 9 13 18 43 55 43 选择排序方法 1 2 3 4 5 6 7 7 9 13 18 43 55 43 第六趟：从2个元素中选出最小者，将其换入位置6，过程为：min为最小元素的位置序号（初值为6），令a(min)表示最小元素的值（初值为位置6的元素），逐一比较，找出最小元素及其位置 位置7的元素最小 交换 1 2 3 4 5 6 7 7 9 13 18 43 43 55 选择排序方法 1 2 3 4 5 6 7 43 18 9 13 55 7 43 以7个元素为例，经过6趟选择，将元素排列有序 排序 1 2 3 4 5 6 7 7 9 13 18 43 43 55 1. 在a(i)、a(i+1)、…a(n)中通过比较找到存放最小数的位置t 的代码实现 ‘最小数存放位置min预设为I（i）号位置 ‘从2(也就是i+1)号到n号的元素为止，每个元素与min号元素比较，如果有哪个元素比min号元素小，那么用变量min记录这个元素号。 ‘用变量j来表示当前用以比较的元素的位置。 For j = i + 1 To n If d(j) d(t) Then t = j Next j min = i 选择排序算法 7个元素进行选择排序时，需要六趟，用i表示趟数 i ← 1 i=6? 结束 Y i ← i+1 N 进行第i趟选择排序 开始 选择排序算法 7个元素进行选择排序时，需要六趟，用i表示趟数 i ← 1 i=6? 结束 Y i ← i+1 N min表示最小元素的位置 min ← i, j ← i+1 比较a(min)和a(j) 如果a(j)a(min)则令min= j j ← j+1 N Y 交换a(min)和a(i) 开始 j=7? 选择排序算法 i ← 1 i=6? 结束 Y i ← i+1 N min← i, j ← i+1 比较a(min)和a(j) 如果a(j)a(min)则令min= j j ← j+1 N Y 交换a(min)和a(i) 开始 j=7? For i = 1 To n - 1 min = i For j = i + 1 To n If a(j) a(min) Then min = j