53数据排序-选择课件高二上学期选择性必修1《数据与数据结构》第五章浙教版

5.5数据排序–选择排序（升序为例）《数据与数据结构》一、选择排序基本思想：是对参加排序的数组中所有元素中找出最小（或最大）的数据，使它与第一个（或最后一个）元素中的数据进行相互交换位置。然后在余下的元素中找出最小（或最大）的数据，与第二个（或最后第二个）元素中的数据交换位置。以此类推，直到所有元素称为一个有序的序列。一、选择排序过程每趟排序后数组a的值分别为：第1趟：[1,9,3,8,5,2]第2趟：[1,2,3,8,5,9]第3趟：[1,2,3,8,5,9]第4趟：[1,2,3,5,8,9]第5趟：[1,2,3,5,8,9]一、选择排序过程注意：红色标记最小值

绿色标记待排序区间

黄色标记有序区间三、选择排序和冒泡排序

对比小结冒泡排序选择排序排序遍数比较次数交换次数时间复杂度n-1n-1(n-1)*n/2(n-1)*n/2逆序对数量<=n-1O(n2)O(n2)选择排序的比较次数与待排序元素的初始状态无关，而交换次数与待排序元素的初始状态有关，当待排序元素已经有序时，交换

0次，最坏情况下交换n-1次。一、选择排序程序实现(以升序为例)i=0;min=?forjinrange(1,?)#依次比较找最小值的下标ifa[j]

?

a[min]:#升序排序min=jifmin!=?:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值i=0;min=0forjinrange(1,6)#依次比较找最小值的下标ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值一、选择排序程序实现(以升序为例)i=1;min=?#假设待排序区间第一个元素为擂主forjinrange(?,?)#依次比较找最小值的下标ifa[j]

?

a[min]:#升序排序min=jifmin!=?:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值i=1;min=1#假设待排序区间第一个元素为擂主forjinrange(2,6)#依次比较找最小值的下标ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值一、选择排序程序实现(以升序为例)i=2;min=?forjinrange(?,?)#依次比较找最小值的下标ifa[j]

<

a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值i=2;min=2forjinrange(3,6)#依次比较找最小值的下标ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值一、选择排序程序实现(以升序为例)i=3;min=?forjinrange(?,?)#依次比较找最小值的下标ifa[j]

<

a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值i=3;min=3forjinrange(4,6)#依次比较找最小值的下标ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值一、选择排序程序实现(以升序为例)i=4;min=?forjinrange(?,?)#依次比较找最小值的下标ifa[j]

<

a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值i=4;min=4forjinrange(5,6)#依次比较找最小值的下标ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值一、选择排序程序实现(6个元素升序为例)i=0;min=0#第一趟排序forjinrange(1,6)#依次比较找最小值的下标ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值i=1;min=1#第二趟排序forjinrange(2,6)#依次比较找最小值的下标ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值i=2;min=2#第三趟排序forjinrange(3,6)#依次比较找最小值的下标ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值i=3;min=3#第四趟排序forjinrange(4,6)#依次比较找最小值的下标ifa[j]

<a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值i=4;min=?#第五趟排序forjinrange(5,6)#依次比较找最小值的下标ifa[j]

<

a[min]:#升序排序min=jifmin!=i:a[min],a[i]=a[i],a[min]

#交换a[min]与a[i]的值n=len(a)

#n个元素规模升序排序

做个笔记宝典P82foriinrange(?)#外循环表示排序趟次

min=?#假设待排序区间第一个元素为擂主

forjinrange(?,?):#将每个元素跟当前擂主PK

ifa[j]

?

a[min]:#PK成功则更换擂主min=j

#更换擂主ifmin!=i

:a[min],a[i]=a[i],a[min]

#交换n-1ii+1n<二、选择排序和冒泡排序

程序对比小结n=len(a)

#选择排序

顺序扫描foriinrange(n-1)#排序最多n-1趟

min=i#假设待排序区间第一个元素为擂主

forjinrange(i+1,n):#将每个元素跟当前擂主PK

ifa[j]

<

a[min]:#PK成功则更换擂主

升序

min=j

#更换擂主ifmin!=i

:

a[min],a[i]=a[i],a[min]

#交换n=len(a)#冒泡排序

逆序扫描foriinrange(n-1):#排序n-1趟

forjinrange(n-1,i,-1):#从后往前扫描ifa[j-1]>a[j]:#相邻元素比较

升序

a[j],a[j-1]=a[j-1],a[j]#交换选择与冒泡排序的最大区别:选择排序待排序区间内的元素a[min]能与最左端（或最右端）的元素a[i]发生交换，冒泡排序是相邻元素交换。对比两段程序，为何选择排序更高效，主要就是因为有min变