3.5选择排序算法及程序实现.ppt

1．选择排序算法的概念 选择排序算法是对冒泡排序算法的改进。这种方法是对参加排序数组的所有元素中找出最小(或最大)数据的元素，使它与第一个元素中数据相互交换位置。然后在余下的元素中找出最小(或最大)的数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。 某数组d共有4个元素构成，每个元素的值如下表所示： 3．5 选择排序算法及程序实现 数组元素 d(1) d(2) d(3) d(4) 值 105 123 97 72 用选择排序法按升序进行排序的过程，从数组第一个元素开始起： 第1遍：寻找从d(1)到d(4)范围内的最小数据d(k)，即k＝4，将d(1)与d(k)互换数据： 共比较数据3次，交换数据1次。 第2遍：寻找从d(2)到d(4)范围内的最小数据d(k)，即k＝3，将d(2)与d(k)互换数据： 共比较数据2次，交换数据1次。 第3遍：寻找从d(3)到d(4)范围内的最小数据d(k)，即k＝4，将d(3)与d(k)互换数据： 总共比较数据1次，交换数据1次。 显然，通过上述3遍处理，数组d中最小、第2小、第3小的数据已经分别存储在数组元素d(1)、d(2)、d(3)中，即数组元素d(1)到d(3)变为有序，而剩下的d(4)中的数据自然是数组中的最大数据。因此，通过3遍这样的处理，整个数组内的数据将是有序的。 4个元素共需进行3遍加工处理，总的比较次数为3＋2＋1＝6次，而总计交换次数每一遍一次，共计只有3次。 对于n个元素的数组，用选择算法进行排序时，比较次数与冒泡算法相同，但交换的次数比冒泡排序要少，因此它具有较高的效率。 2．选择排序算法的程序实现 选择排序的程序同样采用双重For循环嵌套来实现，外循环来控制是第几遍加工，内循环用来控制数组内进行排序元素的下标变化范围。在每一遍加工结束，都需要用一个变量来存储这一遍加工中所找出的最小(或最大)的数据在数组内的下标。 现有n个数据，分别存放在数组变量a(1 To n)当中，采用选择排序算法程序实现其从小到大的程序结构如下： 实现该算法的程序段如下： 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 ik Then t＝a(i)：a(i)＝a(k)：a(k)＝t 　End If Next i 当外循环变量i取1时，为第1遍加工，k＝1，先假设第1个数据元素为最小值，内循环从第2个数开始比较，如果a(2)小于a(1)，则将a(2)的下标赋值给k，否则k值不变，这个方法目的是保证k是本遍加工最小数据元素的下标。这样，内循环一次完成之后，判断k是不是a(1)的下标1，如果不是，则把a(k)与a(1)的数据进行交换，否则就不进行交换。这样，第1遍加工后，就能把最小的数据存放在a(1)中。当外层循环变量i取2时，为第2遍加工，找出a(2)到a(n)之间的最小数，记录好它的下标k，把最小的数据放到a(2)中。这样，每遍加工，都能找出最小数的下标k，比较是不是i，如果不是，就将a(k)与a(i)交换。经过n－1遍之后，就能实现从小到大的排序。 选择排序的关键在于最小值变量k的值在不断的发生变化，而每一遍加工，最多只交换一次数据，所以排序的效率比冒泡排序要高。 本节的学习要求掌握选择排序的基本思想，能根据选择排序的思想来进行选择排序的操作。掌握用程序来实现选择排序的算法，能根据生活中的实际要求编写选排排序的程序，从而进一步熟悉多重循环程序的编写。考查方式为选择题与填空题。 用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为166、169、177、175、172，则下列选项中可能是原始数据序列的是 (　　) A．175、177、169、166、172 B．177、169、166、175、172 C．166、177、169、175、172 D．166、169、172、175、177 B 2．有6位裁判为运动员评分，给出的分数分别为48、45、63、46、59、57。采用选择排序算法对其进行排序，若完成第一遍时的结果为：63、45、48、46、59、57，则完成第二遍时的结果是 (　　) A．63、45、48、46、59、57 B．63、59、57、48、45、46 C．63、59、57、46、45、48 D．63、59、48、46、45、57 D 3．某校通过政府招投标中心采购一套多媒体教学设备，有5家单位参加竞标，竞标价分别为18万、17万、23万、15万、16万元人民币。若采用选择排序算法对标价从大到小排序，需要进行数据互换的次数是