"""
遍历数组
交换旗帜变量 = 假 （False）
从 i = 1 到 最后一个没有排序过元素的指数
如果 左边元素 > 右边元素
交换（左边元素，右边元素）
交换旗帜变量 = 真（True）
"""
def bubble_sort(arr):
for i in range(len(arr)):
flag = False
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
flag = True
# 如果没有数据交换则表示已经有序，退出循环
if not flag:
break
return arr
"""
将第一个元素标记为已排序
遍历每个没有排序过的元素
“提取” 元素 X
i = 最后排序过元素的指数 到 0 的遍历
如果现在排序过的元素 > 提取的元素
将排序过的元素向右移一格
否则：break
插入提取的元素
"""
def insert_sort(arr):
if len(arr) <= 1:
return arr
# 遍历每个未排序元素
for i in range(1, len(arr)):
val = arr[i]
j = i - 1
while j >= 0:
if arr[j] > val:
arr[j + 1] = arr[j]
else:
break
j -= 1
arr[j + 1] = val
return arr
"""
重复（元素个数-1）次
把第一个没有排序过的元素设置为最小值
遍历每个没有排序过的元素
如果元素 < 现在的最小值
将此元素设置成为新的最小值
将最小值和第一个没有排序过的位置交换"""
def select_sort(arr):
for i in range(len(arr)-1):
min_idx, min_val = i, arr[i]
for j in range(i, len(arr)):
if arr[j] < min_val:
min_idx, min_val = j, arr[j]
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
from random import randint
arr = [randint(1,100) for i in range(10)]
%time bubble_sort(arr)
%time insert_sort(arr)
%time select_sort(arr)
CPU times: user 18 µs, sys: 1e+03 ns, total: 19 µs
Wall time: 19.8 µs
CPU times: user 8 µs, sys: 0 ns, total: 8 µs
Wall time: 10 µs
CPU times: user 14 µs, sys: 1 µs, total: 15 µs
Wall time: 16.9 µs
[17, 17, 22, 29, 56, 61, 89, 90, 91, 97]
- 插入排序,选择排序,冒泡排序都是O(n^2)的算法，但是插入排序的交换次数更少，更省时间
- 选择排序是不稳定的算法，相同大小的值排序前后顺序可能会不同
- 算法可视化站点https://visualgo.net/zh/sorting