2.排序算法（2）

1.选择排序介绍

属于选择排序
两两比较大小，找出极值对应的索引，并将其放置到固定位置

升序：

1. min_index从0开始，lst[min_index]与lst[1]比较，将数值小的赋予min_index。以此类推，直至完lst[min_index]与lst[n-1]比较比较.
    min_index记录的值为最小值，在将lst[0]和lst[min_index]进行数值交换，将最小值放置到lst[0]位置，共比较了n-1次。
2. min_index从1开始，lst[min_index]与lst[2]比较，将数值小的赋予min_index。以此类推，直至完lst[min_index]与lst[n-1]比较比较.。
...
3. 直至min_index从n-2开始，只需要比较lst[min_index]和lst[n-1]，即完成比较。

动态效果：https://www.runoob.com/w3cnote/bubble-sort.html

2.代码实现

版本1：

lst0 = 
[
[2,5,23,6,0,78,68],
[5,2,23,0,6,78,68],
[0,2,5,6,23,68,78]
]

lst = lst0[0]
length = len(lst)
print(1,length,lst)

for i in range(len(lst)):
    min_index = i
    for j in range(i+1,len(lst)):
        if lst[min_index] > lst[j]:
            min_index = j
    lst[min_index],lst[i] = lst[i],lst[min_index]

print(lst)

# 运行结果
[2, 5, 23, 6, 0, 78, 68]
[0, 2, 5, 6, 23, 68, 78]

版本2：对比较和交换的次数进行统计

lst0 = 
[
[2,5,23,6,0,78,68],
[5,2,23,0,6,78,68],
[0,2,5,6,23,68,78]
]

lst = lst0[1]
print(lst)

count_iter = 0  # 用于统计比较的次数
count_swap = 0  # 用于统计交换总次数

for i in range(len(lst)):
    min_index = i
    for j in range(i+1,len(lst)):
        count_iter += 1
        if lst[min_index] > lst[j]:
            min_index = j
    if i != min_index:  # 进行交换之前进行比较
        lst[min_index],lst[i] = lst[i],lst[min_index]
        count_swap += 1

print('count_iter = {}'.format(count_iter))
print('count_swap = {}'.format(count_swap))
print(lst)

# 执行结果  lst[0][0]
[2, 5, 23, 6, 0, 78, 68]
count_iter = 21
count_swap = 4
[0, 2, 5, 6, 23, 68, 78]

# 执行结果  lst[0][1]
[5, 2, 23, 0, 6, 78, 68]
count_iter = 21
count_swap = 4
[0, 2, 5, 6, 23, 68, 78]

# 执行结果  lst[0][2]
[0, 2, 5, 6, 23, 68, 78]
count_iter = 21
count_swap = 0
[0, 2, 5, 6, 23, 68, 78]

版本3：二元选择排序，一次循环固定左侧最小值和右侧最大值

lst0 = [[2,5,23,6,0,78,68],[5,2,23,0,6,78,68],[0, 2, 5, 6, 23, 68, 78]]

lst = lst0[2]
length = len(lst)
print(lst)


count_iter = 0  # 用于统计循环总次数
count_swap = 0  # 用于统计交换总次数


for i in range(length//2):
    max_index = i
    min_index = -i-1
    min_origin = min_index

    for j in range(i+1,length-i):
        count_iter += 1
        if lst[max_index] > lst[j]:
            max_index = j
        if lst[min_index] < lst[-j-1]:
            min_index = -j-1

    if i != max_index:
        lst[i],lst[max_index] = lst[max_index],lst[i]
        count_swap += 1
        if i == min_index or i == length + min_index:
            min_index = max_index

    if min_origin != min_index:
        lst[min_origin],lst[min_index] = lst[min_index],lst[min_origin]
        count_swap += 1

print('count_iter = {}'.format(count_iter))
print('count_swap = {}'.format(count_swap))
print(lst)

# 执行结果  lst[0][0]
[2, 5, 23, 6, 0, 78, 68]
count_iter = 12
count_swap = 5
[0, 2, 5, 6, 23, 68, 78]

# 执行结果  lst[0][1]
[5, 2, 23, 0, 6, 78, 68]
count_iter = 12
count_swap = 4
[0, 2, 5, 6, 23, 68, 78]

# 执行结果  lst[0][2]
[0, 2, 5, 6, 23, 68, 78]
count_iter = 12
count_swap = 0
[0, 2, 5, 6, 23, 68, 78]

3. 总结

1.简单选择排序需要根据一轮轮比较，并在每一轮中发现极值
2.时间复杂度O(n^2)
3.无法知道当前是否已经达到排序要求，但可以知道极值是否在目标索引位置上
4.减少交换次数，提高效率，性能略胜于冒泡法