算法实例选择排序法课件.ppt

《算法实例选择排序法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法实例选择排序法临沭县实验中学1．选择排序算法的概念选择排序算法是对冒泡排序算法的改进。这种方法是对参加排序数组的所有元素中找出最小(或最大)数据的元素，使它与第一个元素中数据相互交换位置。然后在余下的元素中找出最小(或最大)的数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。某数组d共有4个元素构成，每个元素的值如下表所示：数组元素d(1)d(2)d(3)d(4)值1051239772用选择排序法按升序进行排序的过程，从数组第一个元素开始起：第1遍：寻找从d(1)到

2、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)变为有

3、序，而剩下的d(4)中的数据自然是数组中的最大数据。因此，通过3遍这样的处理，整个数组内的数据将是有序的。4个元素共需进行3遍加工处理，总的比较次数为3＋2＋1＝6次，而总计交换次数每一遍一次，共计只有3次。对于n个元素的数组，用选择算法进行排序时，比较次数与冒泡算法相同，但交换的次数比冒泡排序要少，因此它具有较高的效率。2．选择排序算法的程序实现选择排序的程序同样采用双重For循环嵌套来实现，外循环来控制是第几遍加工，内循环用来控制数组内进行排序元素的下标变化范围。在每一遍加工结束，都需要用一个变量来

4、存储这一遍加工中所找出的最小(或最大)的数据在数组内的下标。现有n个数据，分别存放在数组变量a(1Ton)当中，采用选择排序算法程序实现其从小到大的程序结构如下：实现该算法的程序段如下：Fori＝1Ton－1k＝iForj＝i＋1tonIfa(j)kThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNexti当外循环变量i取1时，为第1遍加工，k＝1，先假设第1个数据元素为最小值，内循环从第2个数开始比较，如果a(2)小于a(1)，则将a(2)的

5、下标赋值给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遍之后，就能实现从小到大的排序。

6、选择排序的关键在于最小值变量k的值在不断的发生变化，而每一遍加工，最多只交换一次数据，所以排序的效率比冒泡排序要高。选择排序方法1234567431891355743以7个元素为例说明选择排序位置1~位置7的元素初始排列如下所示选择排序实例1234567431891355743第一趟：从7个元素中选出最小者，将其换入位置1，过程为：令min_elem表示最小元素（初值为位置1的元素），k为最小元素的位置序号（初值为1），逐一比较，找出最小元素及其位置位置6的元素最小交换12345677439135543

7、431234567718913554343第二趟：从6个元素中选出最小者，将其换入位置2，过程为：令min_elem表示最小元素（初值为位置2的元素），k为最小元素的位置序号（初值为2），逐一比较，找出最小元素及其位置位置3的元素最小交换12345677918135543431234567791813554343第三趟：从5个元素中选出最小者，将其换入位置3，过程为：令min_elem表示最小元素（初值为位置3的元素），k为最小元素的位置序号（初值为3），逐一比较，找出最小元素及其位置位置4的元素最小交

8、换12345677913185543431234567791318554343第四趟：从4个元素中选出最小者，将其换入位置4，过程为：令min_elem表示最小元素（初值为位置4的元素），k为最小元素的位置序号（初值为4），逐一比较，找出最小元素及其位置位置4的元素最小交换12345677913185543431234567791318554343第五趟：从3个元素中选出最小者，将其换入位置5，过程为：令min_elem表示最小元素（初值为