选择排序基本概念

• 1.选择排序
• • 1.1 基本概念
  • 1.2 选择排序执行步骤有
  • 1.3 对于5个元素的值步骤次数
  • 1.4 选择排序大O记法表示
• 2. 将[4,2,7,1,3]进行选择排序 【实战】
• • 2.1 第一次轮回步骤
  • 2.2 第二次轮回步骤
  • 2.3 第三次轮回步骤
  • 2.4 第四次轮回步骤
• 3.选择排序代码实现
• • 3.1 根据最小值排序
  • 3.2 根据最大值排序

1.选择排序

1.1 基本概念

• 选择排序效率比冒泡排序高，但是大O记法一样
• 操作步骤
  • 根据最小值
    • 从左至右依次检查数据，找出值最小的那个。
    • 在此过程中，会用一个变量记录检查过的最小值的索引，如果未检查的数值小于最小值，就把最小值改为新的索引
  • 根据最大值
    • 从左至右依次检查数据，找出值最大的那个。
    • 在此过程中，会用一个变量记录检查过的最大值的索引，如果未检查的数值大于最大值，就把最大值改为新的索引

1.2 选择排序执行步骤有

• 比较：比较值
• 交换：交换值

1.3 对于5个元素的值步骤次数

• 总步骤为：（4+3+2+1)+1*4=14

1.4 选择排序大O记法表示

• 发现，随着N的增长，步数大致增长为N22\frac{N^2}{2}2N2​
• 选择排序的大O记法：O(N2N^2N2)【大O记法忽略常数】

2. 将[4,2,7,1,3]进行选择排序 【实战】

• 会进行4次循环(轮回)
• 选择最小值进行排序

2.1 第一次轮回步骤

2.2 第二次轮回步骤

2.3 第三次轮回步骤

2.4 第四次轮回步骤

3.选择排序代码实现

3.1 根据最小值排序

# 方式一
alist = [4, 2, 7, 1,3]
def sort(alist):for i in range(len(alist)-1):min_index = i  # 记录最小值索引for j in range(i+1,len(alist)):if alist[j]i + 1}次轮回结果为:", alist)
sort(alist)# 方式二
alist = [4, 2, 7, 1,3]
def sort(alist):for i in range(len(alist)-1):min_index = i  # 记录最小值索引for j in range(i+1,len(alist)):if alist[j]i + 1}次轮回结果为:", alist)
sort(alist)

3.2 根据最大值排序

# 方式一
alist = [3, 8, 5, 7, 6]
def sort(alist):for i in range(len(alist)-1):max_index = 0for j in range(1,len(alist)-i):if alist[j]>alist[max_index]:max_index = j       #找出最大值，将最大值索引赋值给max_index# 最大值和最后一位交换位置alist[len(alist)-1-i],alist[max_index]=alist[max_index],alist[len(alist)-1-i]print(f"第{i + 1}次轮回结果为:", alist)
sort(alist)# 方式二
alist = [3, 8, 5, 7, 6]
def sort(alist):for i in range(len(alist) - 1):max_index = 0for j in range(1, len(alist) - i):if alist[j] > alist[max_index]:max_index = j  # 找出最大值，将最大值索引赋值给max_index# 最大值和最后一位交换位置if max_index != i: # 索引变，交换位置，不变不交换alist[len(alist) - 1 - i], alist[max_index] = alist[max_index], alist[len(alist) - 1 - i]print(f"第{i + 1}次轮回结果为:", alist)
sort(alist)