课件17张PPT。选择排序一：什么是选择排序（selection sort）选择排序是对冒泡排序算法的改进，在参加排序的所有数组元素中找出最小数据的元素，使它与第一个元素中的数据相互交换位置。然后再在余下的元素中找出最小数据的元素，与第二个元素中的数据相互交换位置，以此类推，直到所有元素成为一个有序的序列。此方法中交换的次数比冒泡排序少，具有较高的效率。选择排序的实现过程a(1)a(2)a(3)a(4)a(5)i=1(用变量i表示第一遍处理，也表示第一个数据元素) 在第1至第5个数组元素中找最小数据 (最小数据的下标用变量k表达,首先默认最小数据a(k)为第一个数据，然后余下的4个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标) 如果找到的最小数据下标k不是1(i)的话，那么与第一个数据元素发生交换(如果k<>i(i=1)，则a(k)与a(i)交换) 结果(第一个位置中的数据值最小，a(2)~a(5)为无序区域)i=1 k=1 for j=2 to 5 if a(j)
i then t=a(k): a(k)=a(i):a(i)=t End if第一遍排序选择排序的实现过程a(1)a(2)a(3)a(4)a(5)i=2用变量i表示第二遍处理，也表示第二个数据元素) 在第2至第5个数组元素中找最小数据 (最小数据的下标用变量k表达,首先默认最小数据a(k)为第二个数据，然后余下的3个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标) 如果找到的最小数据下标k不是2(i)的话，那么与第二个数据元素发生交换(如果k<>i(i=2)，则a(k)与a(i)交换) 结果(第一个位置中的数据值最小，a(3)~a(5)为无序区域)i=2 k=2 for j=3 to 5 if a(j)i then t=a(k): a(k)=a(i):a(i)=t End if第二遍排序选择排序的实现过程a(1)a(2)a(3)a(4)a(5)i=3用变量i表示第三遍处理，也表示第三个数据元素) 在第3至第5个数组元素中找最小数据 (最小数据的下标用变量k表达,首先默认最小数据a(k)为第三个数据，然后余下的2个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标) 如果找到的最小数据下标k不是3(i)的话，那么与第三个数据元素发生交换(如果k<>i(i=3)，则a(k)与a(i)交换) 结果(第一个位置中的数据值最小，a(4)~a(5)为无序区域)i=3 k=3 for j=4 to 5 if a(j)i then t=a(k) a(k)=a(i) a(i)=t End if第三遍排序选择排序的实现过程a(1)a(2)a(3)a(4)a(5)i=4用变量i表示第四遍处理，也表示第四个数据元素) 在第4至第5个数组元素中找最小数据 (最小数据的下标用变量k表达,首先默认最小数据a(k)为第四个数据，然后余下的1个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标) 如果找到的最小数据下标k不是4(i)的话，那么与第四个数据元素发生交换(如果k<>i(i=4)，则a(k)与a(i)交换) 结果(第一个位置中的数据值最小，a(5)~a(5)为无序区域)i=4 k=4 for j=5 to 5 if a(j)i then t=a(k) a(k)=a(i) a(i)=t End if第四遍排序5个数据进行选择排序的程序代码For i=1 to 4 k=i for j=i+1 to 5 if a(j)i then t=a(k):a(k)=a(i):a(i)=t End if Next i对数组d中的n个数进行升序排序，其程序代码如下：For i=1 to n-1 k=i for j=i+1 to n if a(j)i then t=a(k):a(k)=a(i):a(i)=t End if Next i对数组d中的n个数进行降序排序，其方框处程序代码如何修改思考：在i到n中定位最小数的位置如果k<>i，则a(k)与a(i)交换课 堂 练 习1、某数组10个元素，依次为2、20、12、15、13、50、55、60、80、30，若采用选择排序算法进行降序排序，则第4遍排序完成时的数据序列为 （ ）B. 80、60、55、50、13、15、12、20、2、30A. 80、60、55、50 ... ... 
