算法之选择排序

算法之选择排序

简单选择排序

• 选择排序
  • 每一趟两两比较大小，找出极值(极大值或极小值)并放置到有序区的位置。

核心算法

• 结果可为升序或降序排列，默认升序排列。以降序为例
• 扩大有序区，减小无序区。图中红色部分就是增大的有序区，反之就是减小的无序区
• 相邻元素依次两两比较，获得每一次比较后的最大值，并记住此值的索引
• 每一趟都从无序区中选择出最大值，然后交换到当前无序区最左端

nums = [1, 9, 8, 5]
print(nums)
length = len(nums)

for i in range(length - 1): 	# i = 0
    maxindex = i 				# i = 0 假定最大数索引就是当前索引 i=0
    for j in range(i+1, length): # 取值范围就是索引 1,2,3 后不包没有，没有0是这些值和索引0进行比较。
        if nums[j] > nums[maxindex]:
            maxindex = j 		# 将最大索引赋值给maxindex
            
    nums[i], nums[maxindex] = nums[maxindex], nums[i] # 将索引交换，最大数放到最前方
    print(nums, i, maxindex)
    if i == 0: break			# 循环终止条件，交换一次终止。

执行结果：[1, 9, 8, 5] # 代码第2行打印的nums的值
执行结果：[9, 1, 8, 5] 0 1  # break 终止的第一次交换

nums = [1, 9, 8, 5]
print(nums)
length = len(nums)

for i in range(length - 1): 	# i = 0
    maxindex = i 				# i = 0 假定最大数索引就是当前索引 i=0
    for j in range(i+1, length): # 取值范围就是索引 1,2,3 后不包没有，没有0是这些值和索引0进行比较。
        if nums[j] > nums[maxindex]:
            maxindex = j 		# 将最大索引赋值给maxindex
            
    nums[i], nums[maxindex] = nums[maxindex], nums[i] # 将索引交换，最大数放到最前方
    print(nums, i, maxindex)

执行结果：[1, 9, 8, 5] # 代码第2行打印的nums的值
执行结果：[9, 1, 8, 5] 0 1
执行结果：[9, 8, 1, 5] 1 2
执行结果：9, 8, 5, 1] 2 3

上面代码中我们就实现了选择排序

选择排序优化

# 变种：选择排序
    # 一次确定最大数与最小数

num_list = [[1, 9, 8, 5], [9, 1, 8, 5]] 	# 列表套列表
nums = num_list[1] 							# 选择排序的列表，也就是索引1的列表
print(nums)
length = len(nums)

count_iter = 0 			# 比较次数
count_swap = 0 			# 交换次数

for i in range(length // 2):	 # 2个数找1次，3个数找1次，4个数找2次，5个数找2次，这就是为什么整除2
    maxindex = i				 # i = 0 假定最大数索引就是当前索引 i=0
    minindex = -i-1 			 # min = -1
    
    # j循环作用记住极大值的索引和极小值的索引
    for j in range(i+1, length): 	# 取值范围就是索引 1,2,3 后不包没有，没有0是这些值和索引0进行比较。
        count_iter += 1 			# 比较次数
        if nums[j] > nums[maxindex]:
            maxindex = j 			# 将最大索引赋值给maxindex
        if nums[minindex] > nums[-j-1]:
            minindex = -j-1 		# 负索引 -1就是最后一个索引
    print(maxindex, minindex, '+++')
    
    if i != maxindex: 				# 进行条件判断，索引0小于1-2-3才进行交换
        nums[i], nums[maxindex] = nums[maxindex], nums[i] # 将索引交换，最大数放到最前方
        count_swap += 1 			# 交换次数
        
    break 							# 执行一次就终止

执行结果：[9, 1, 8, 5]
执行结果：0 -3 +++

num_list = [[1, 9, 8, 5], [9, 1, 8, 5]] 	# 列表套列表
nums = num_list[1] 							# 选择排序的列表，也就是索引1的列表
print(nums)
length = len(nums)

count_iter = 0 			# 比较次数
count_swap = 0 			# 交换次数

for i in range(length // 2): 	# 2个数找1次，3个数找1次，4个数找2次，5个数找2次，这就是为什么整除2
    maxindex = i 				# i = 0 假定最大数索引就是当前索引 i=0
    minindex = -i-1 			# min = -1
    minorigin = minindex 		# 减少计算量
    
    # j循环作用记住极大值的索引和极小值的索引
    for j in range(i+1, length): 	# 取值范围就是索引 1,2,3 后不包没有，没有0是这些值和索引0进行比较。
        count_iter += 1 			# 比较次数
        if nums[j] > nums[maxindex]:
            maxindex = j 			# 将最大索引赋值给maxindex
        if nums[minindex] > nums[-j-1]:
            minindex = -j-1 		# 负索引 -1就是最后一个索引
    print(maxindex, minindex, '+++')
    
    if i != maxindex: 				# 进行条件判断，索引0小于1-2-3才进行交换
        nums[i], nums[maxindex] = nums[maxindex], nums[i] # 将索引交换，最大数放到最前方
        count_swap += 1 			# 交换次数
        
    if minorigin != minindex:
        nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
        count_swap += 1
        
    
    print(nums, i, maxindex)
    
print('_' * 30)
print(nums, count_iter, count_swap)

执行结果：
[9, 1, 8, 5]
0 -3 +++
[9, 5, 8, 1] 0 0
2 -3 +++
[9, 5, 8, 1] 1 2
______________________________
[9, 5, 8, 1] 5 3  

最后得到的结果并不是按序排的

num_list = [[1, 9, 8, 5], [9, 1, 8, 5]]	 	# 列表套列表
nums = num_list[1] 							# 选择排序的列表，也就是索引1的列表
print(nums)
length = len(nums)

count_iter = 0			 # 比较次数
count_swap = 0 			 # 交换次数

for i in range(length // 2): 	# 2个数找1次，3个数找1次，4个数找2次，5个数找2次，这就是为什么整除2
    maxindex = i 				# i = 0 假定最大数索引就是当前索引 i=0
    minindex = -i-1 			# min = -1
    minorigin = minindex 		# 减少计算量
    
    # j循环作用记住极大值的索引和极小值的索引
    for j in range(i+1, length): 	# 取值范围就是索引 1,2,3 后不包没有，没有0是这些值和索引0进行比较。
        count_iter += 1 			# 比较次数
        if nums[j] > nums[maxindex]:
            maxindex = j			# 将最大索引赋值给maxindex
        if nums[minindex] > nums[-j-1]:
            minindex = -j-1 		# 负索引 -1就是最后一个索引
    print(maxindex, minindex, '+++')
    
    if i != maxindex: 				# 进行条件判断，索引0小于1-2-3才进行交换
        nums[i], nums[maxindex] = nums[maxindex], nums[i] # 将索引交换，最大数放到最前方
        count_swap += 1 			# 交换次数
        
        # 重要的事说3遍
        # 克服交换对最小值所以的干扰
        # 克服交换对最小值所以的干扰
        # 克服交换对最小值所以的干扰
        if i == minindex or i == length + minindex: # 条件 i是最小值 或 i 是长度+最小值
            minindex = maxindex - length  			# 最小值就等于 最大值减长度
        
    if minorigin != minindex:
        nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
        count_swap += 1
        
    
    print(nums, i, maxindex)
    
print('_' * 30)
print(nums, count_iter, count_swap)

执行结果：
[9, 1, 8, 5]
0 -3 +++
[9, 5, 8, 1] 0 0
2 -3 +++
[9, 8, 5, 1] 1 2
______________________________
[9, 8, 5, 1] 5 2