Python 选择排序

一、简单选择排序

1.1 简单选择排序

• 属于选择排序
• 两两比较大小，找出极值（极大值或极小值）被放置在固定的位置，这个固定位置一般指的是某一端
• 结果分为升序和降序排列

1.2 降序

• n 个数从左至右，索引从 0 开始到 n-1，两两一次比较，记录大值索引，此轮所有数比较完毕，将大数和索引 0 数交换，若大数就是索引 0，不交换，第二轮，从 1 开始比较，找到最大值，将它和索引 1 位置交换，若它就在索引 1 位置则不交换，以此类推，每次左边都会固定下一个大数

1.3 升序

• 和降序相反

示例.png

1.4 简单排序实现

nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)

for i in range(length):
    maxindex = i
    for j in range(maxindex + 1, length):
        if nums[j] > nums[maxindex]:
            maxindex = j
    nums[i], nums[maxindex] = nums[maxindex], nums[i]
print(nums)

二、优化实现

2.1 二元选择排序，同时固定左边最大值和右边最小值

• 优点
  • 减少迭代元素的次数
  • length//2，通过几次运算就可发现规律
  • 由于使用了负索引，为了计算方便，所以增加了转换为正索引

nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)

for i in range(length // 2):
    maxindex = i
    minindex = -i -1
    minorigin = length + minindex
    for j in range(i + 1, length - i):   # 每次左右各减少一个
        if nums[j] > nums[maxindex]:
            maxindex = j
        if nums[-j -1] < nums[minindex]:
            minindex = -j -1
    else:
        minindex = length + minindex   # 调整为正索引
    if i != maxindex:
        nums[i], nums[maxindex] = nums[maxindex], nums[i]
        if i == minindex:
            minindex = maxindex   # 若最小值交换过，变更索引
    if minindex != minorigin:
        nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
print(nums)

2.2 针对最大最小值相等优化

• 若一轮比较后，极大值、极小值相等，说明比较的序列元素全部相等，则跳出循环

nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)

for i in range(length // 2):
    maxindex = i
    minindex = -i -1
    minorigin = length + minindex
    for j in range(i + 1, length - i):   # 每次左右各减少一个
        if nums[j] > nums[maxindex]:
            maxindex = j
        if nums[-j -1] < nums[minindex]:
            minindex = -j -1
    if nums[maxindex] == nums[minindex]:   # 最大最小值相等，跳出循环
        break
    minindex = length + minindex   # 调整为正索引
    if i != maxindex:
        nums[i], nums[maxindex] = nums[maxindex], nums[i]
        if i == minindex:
            minindex = maxindex   # 若最小值交换过，变更索引
    if minindex != minorigin:
        nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
print(nums)

2.3 针对 [1, 1, 1, 1, 2] 优化

• 最小值两个均为 1，不需交换，针对此添加一个判断进行优化

nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)

for i in range(length // 2):
    maxindex = i
    minindex = -i -1
    minorigin = length + minindex
    for j in range(i + 1, length - i):   # 每次左右各减少一个
        if nums[j] > nums[maxindex]:
            maxindex = j
        if nums[-j -1] < nums[minindex]:
            minindex = -j -1
    if nums[maxindex] == nums[minindex]:   # 最大最小值相等，跳出循环
        break
    minindex = length + minindex   # 调整为正索引
    if i != maxindex:
        nums[i], nums[maxindex] = nums[maxindex], nums[i]
        if i == minindex:
            minindex = maxindex   # 若最小值交换过，变更索引
    if minindex != minorigin and nums[minorigin] != nums[minindex]:   # 索引不同，值相等不需交换
        nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
print(nums)

三、简单选择排序总结

• 简单选择排序需要数据一轮轮比较，并在每一轮中发现极值
• 没有办法知道当前轮是否已经达到排序要求，但是可知道极值是否在目标索引位置上
• 遍历次数 1,...,n-1 之和 n(n-1)/2
• 时间复杂度 O(n^2)
• 减少交换次数，提高效率，性能略好与冒泡法