专题04 选择排序算法及VB程序实现（知识梳理）-巅峰冲刺2020年浙江省高考选考信息技术二轮专项提升

专题4 选择排序算法及VB程序实现 一、选择排序的基本思想 如果有n个数要求从小到大排序，操作方法是在所有的元素中选出最小的数据，把它与第一个数据交换，这是第一遍加工（或称第一遍排序），第一遍排序完成后，最小的数据就到了第一位。 第二遍加工是在剩下的n-2个数中选出最小的数，把它与第二个数据交换，第二遍排序完成后，第二小的数就到了第二位。 第三遍加工是在剩下的n-2个数中选出最小的数，把它与第三个数据交换…… n个数需要n-1次排序。（前n-1个位置排好了，排序即已经完成） 二、选择排序与冒泡排序的区别 冒泡排序 选择排序 思想方法 一边比较，一边交换 先选出最大值或最小值，再交换 核心代码 For i = 1 To n-1 For j = n To i + 1 Step -1 If a(j) < a(j - 1) Then temp= a(j) a(j) = a(j - 1) a(j - 1) = temp End If Next j Next i For i = 1 To n-1 k=i For j = i+1 To n If a(j)<a(k) then k=j Next j If k < > i Then temp= a(i):a(i) = a(k):a(k) = temp End If Next i 相同点 ① n 个数都需要 n-1 遍排序，其中变量 i 控制排序的遍数。 ② 比较的次数一样多，都是 n*(n-1) / 2 次。 ③ 最好的情况下，交换的次数一样，都是 0 次。 不同点 边比较边交换，最坏的情况下交换的次数是n*(n-1) / 2次。 先选择再交换，最坏的情况下交换的次数是n-1 次。 如何区分 因为是相邻两数比较，因此代码中有类似“a（j）和 a（j-1）”比较的条件表达式。 因为是先选出最大值或最小值，再交换，因此代码中有寻找最大值或最小值的代码，并且用变量（如 k）来记录该值所在的位置。如果 k < > i则交换。 三、冒泡变式（未优化的选择排序） For i = 1 To n-1 For j = i+1 To n