这个是简单选择排序的升级版,在做简单选择排序的时候我没有考虑到数值相同的问题,所以用了数值作比较并且交换,如果出现相同数值会有排序出错的情况,然后这个版本我更新了一下,是直接找出最大和最小值,并且增加了特殊情况判定进行排序,大大降低了交换的次数,提升了运行.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | """ 二元选择排序 """ import random lst = [random.randint(0,10) for x in range(10)] count_iter = 0 count_swap = 0 for i in range(len(lst)//2): mark = i # 记录无序区第一个值 mark1 = -i - 1 # 记录无序区域最后一个值 mark2 = mark1 for j in range(i+1, len(lst) - i): # 每轮两边都要-1 count_iter += 1 if lst[mark] < lst[j]: # 最大值判断并且交换 mark = j if lst[mark1] > lst[-j-1]: # 最小值判断,并且交换 mark1 = -j-1 if lst[mark] == lst[mark1]: # 最大值和最小值相等 break if mark != i: # 判断最大索引与无序区第一索引是否一致 count_swap += 1 lst[i], lst[mark] = lst[mark], lst[i] if i == mark1 or i == len(lst) + mark1: # 如果最小值被交换过,需要更换索引. mark1 = mark if mark1 != mark2 and lst[mark1] != lst[mark2]: # 判断最小索引与无序区最后索引是否一致 count_swap += 1 lst[mark2], lst[mark1] = lst[mark1], lst[mark2] print(lst, count_iter, count_swap) |