第3节 选择排序及程序实现 考试内容 考试要求 选择排序算法思想 c 选择排序程序实现 c 一、选择排序算法思想 每趟排序是在所有的数据中找出最大(或最小)的数据，与第一个数据交换位置，然后再在剩下的数据中找出最大(或最小)的数据，与第二个数据交换位置，以此类推，直到所有元素成为一个有序序列为止。 n个数据排序共需进行n－1趟(遍)排序。 二、选择排序算法框架 设定：对数组d中的n个数据进行升序排序。 (1)从前往后进行比较 For i ＝ 1 To n － 1———n个排序共进行n－1趟排序 假定i位置上的数为最小数 For j ＝ i ＋ 1 To n———i后面的位置 ———若找到更小的数，则将用k记录此数的位置 Next j If k < > i Then———若i位置上的数不是最小数，则和k位置上的数进行互换 交换d(i)与d(k) End If Next i 注：若要按降序排列，将程序中的语句“If d(k)>d(j)”改为“If d(k) i Then———若i位置上的数不是最小数，则和k位置上的数进行互换 交换d(i)与d(k) End If Next i 注：若要按降序排列，将程序中的语句“If d(k)>d(j)”改为“If d(k) d(j) Then k ＝ j———若找到更小的数，则将用k记录此数的位置 Next j If k < > i Then———若i位置上的数不是最小数，则和k位置上的数进行互换 temp＝d(k)：d(k)＝d(i)：d(i)＝temp End If Next i (2)从后往前进行比较 For i ＝ 1 To n － 1———n个排序共进行n－1趟排序 k ＝ i———假定i位置上的数为最小数 For j ＝ n To i ＋ 1 Step －1———i后面的位置 If d(k) > d(j) Then k ＝ j———若找到更小的数，则将用k记录此数的位置 Next j If k < > i Then———若i位置上的数不是最小数，则和k位置上的数进行互换 temp＝d(k)：d(k)＝d(i)：d(i)＝temp End If Next i 一、选择排序算法思想 理解选择排序的基本思想，学会将待排数据按照选择算法思想进行手工模拟排序。 【典例1】 使用选择排序对下表中9个数据进行排序，排序过程如下所示： 初始数据 100 50 80 70 60 35 90 85 25 第1遍 100 50 80 70 60 35 90 85 25 第2遍 100 90 80 70 60 35 50 85 25 第3遍 则第三遍的排序结果为( ) A.100，90，85，80，70，60，35，50，25 B.100，90，85，70，60，35，50，80，25 C.100，90，85，80，70，60，50，35，25 D.100，90，85，60，70，35，50，80，25 解析 本题主要考查选择排序算法的基本思想。观察第1、2遍的排序结果可知，该选择排序为降序排序，第3遍排序时，数据85与80进行交换，因此第三遍排序后的结果为“100，90，85，70，60，35，50，80，25”，答案为B。 答案 B 【变式训练】 采用选择排序算法对数组d中的8个数据“20，8，6，4，15，3，19，50”进行排序，部分程序如下： For i＝1 To 5 k ＝ i For j＝i＋1 To 8 If d(j)k Then tt＝d(k)：d(k)＝d(i)：d(i)＝tt End If Next j Next i 该程序段执行后，数组元素d(1)～d(8)依次为( ) A.3，4，6，8，15，19，20，50 B.3，4，6，8，15，50，20，19 C.3，4，6，8，15，20，19，50 D.3，4，6，8，15，20，50，19 解析 本题主要考查的是选择排序。根 ... ...
