5.3数据排序_选择课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第五章浙教版（2019）

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-1 n-1 (n-1)*n/2 (n-1)*n/2 逆序对数量 <=n-1 O(n2) O(n2) 选择排序的比较次数与待排序元素的初始状态无关，而交换次数与待排序元素的初始状态有关，当待排序元素已经有序时，交换 0 次，最坏情况下交换n - 1次。 5 一、选择排序程序实现(以升序为例) i=0 ; min=? for j in range(1,?) #依次比较找最小值的下标 if a[j] ? a[min]:#升序排序 min=j if min != ? : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 i=0 ; min=0 for j in range(1,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 给出代码提示环节 6 一、选择排序程序实现(以升序为例) i=1 ; min=? #假设待排序区间第一个元素为擂主 for j in range(?,?) #依次比较找最小值的下标 if a[j] ? a[min]:#升序排序 min=j if min != ? : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 i=1 ; min=1#假设待排序区间第一个元素为擂主 for j in range(2,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 给出代码提示环节 7 一、选择排序程序实现(以升序为例) i=2 ; min=? for j in range(?,?) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 i=2 ; min=2 for j in range(3,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 给出代码提示环节 8 一、选择排序程序实现(以升序为例) i=3 ; min=? for j in range(?,?) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 i=3 ; min=3 for j in range(4,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 给出代码提示环节 9 一、选择排序程序实现(以升序为例) i=4 ; min=? for j in range(?,?) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 i=4 ; min=4 for j in range(5,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 给出代码提示环节 10 一、选择排序程序实现(6个元素升序为例) i=0 ; min=0 #第一趟排序 for j in range(1,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 i=1 ; min=1#第二趟排序 for j in range(2,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 i=2 ; min=2#第三趟排序 for j in range(3,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 i=3 ; min=3#第四趟排序 for j in range(4,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 i=4 ; min=?#第五趟排序 for j in range(5,6) #依次比较找最小值的下标 if a[j] < a[min]:#升序排序 min=j if min != i : a[min],a[i]=a[i],a[min] #交换a[min]与a[i]的值 n=len(a) # n个元素规模升序排序 做个笔记宝典P82 for i in range( ? ) #外循环表示排序趟次 min= ? #假设待排序区间第一个元素为擂主 for j in range( ? , ? ):#将每个元素跟当前擂主PK if a[j] ? a[min]:#PK成功则更换擂主 min=j #更换擂主 if min != i : a[min],a[i]=a[i],a[min] #交换 n-1 i i+1 n < 给出代码提示环节 11 二、选择排序和冒泡排序 程序对比小结 n=len(a) #选择排序 顺序扫描 for i in range(n-1) #排序最多n-1趟 min= i #假设待排序区间第一个元素为擂主 for j in range( i+1 , n ):#将每个元素跟当前擂主PK if a[j] < a[min]: #PK成功则更换擂主 升序 min=j #更换擂主 if min != i : a[min],a[i]=a[i],a[min] #交换 n = len(a) #冒泡排序 逆序扫描 for i in range(n-1): #排序n-1趟 for j in range(n-1,i,-1):#从后往前扫描 if a[j-1] > a[j] : #相邻元素比较 升序 a[j],a[j-1] = a[j-1],a[j]#交换 选择与冒泡排序的最大区别:选择排序待排序区间内的元素a[min]能与最左端（或最右端）的元素a[i]发生交换，冒泡排序是相邻元素交换。 对比两段程序，为何选择排序更高效，主要就是因为有min变量的存在，选择排序通过循环找到最小值以后再交换，而冒泡排序是边比较边交换！ 12 B #排序4趟 i=0,1,2,3 #顺序扫描 #找最小值下标 #把最小值元素与最左端元素交换 比较次数：n*(n-1)/2 交换次数： 第一趟：[2,86,98,65,23] 第二趟：[2,23,98,65,86] 第三趟：[2,23,65,98,86] 第四趟：[2,23,65,86,98] $$