冒泡排序
时间复杂度：O(n2) 算法稳定
- 第一趟，从第一个数开始，相邻两个数比较，大的数交换放后，交换到最后位置得出一个第一大数
- 第二趟，从第一个数开始，相邻两个数比较，大的数交换放后，交换到倒数第二得出一个第二大数
- 第n-1趟，最后的两个数比较得出最小数和倒数第二小数
代码实现点:时时比较，时时交换
def bubble_sort(li):
for i in range(len(li)-1): #第i趟
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange: #这里属于优化，也就是如果这次循环中没有发生一次交换，那么此时已经是有序的
return
li = list(range(10000))
random.shuffle(li)
bubble_sort(li)
选择排序
时间复杂度：O(n2) 算法稳定？
- 第一趟，从第一个数开始，相邻两个数比较，把小的索引位置赋值给min_index变量，循环数和当前小值比较，循环完后会得出一个最小值的索引，然后最小值位置和第一个值位置交换
- 第一趟，从第二个数开始，相邻两个数比较，把小的索引位置赋值给min_index变量，循环数和当前小值比较，循环完后会得出一个第二小值的索引，然后最第二小值位置和第二个值位置交换
- 第n-1趟，最后的两个数比较得出最大数和第二大数，交换
代码实现点：时时存储小值索引，一趟后交换
def select_sort(li):
for i in range(len(li)-1): # i是第几趟
min_loc = i
for j in range(i+1, len(li)):
if li[j] < li[min_loc]:
min_loc = j
li[i], li[min_loc] = li[min_loc], li[i]
print(li)
li = [3,4,2,1,5,6,8,7,9]
print(li)
select_sort(li)
插入排序
时间复杂度：O(n2) 算法稳定？
- 好比打扑克，手里牌已经有序，抓的牌只要插到顺序正确的位置上
代码实现点：记录手里牌的下标和抓到牌的值,利用冒泡的方式去把抓到牌往左冒
def insert_sort(li):
for i in range(1, len(li)): #i 表示摸到的牌的下标
tmp = li[i]
j = i - 1 #j指的是手里的牌的下标
while j >= 0 and li[j] > tmp: #小于当前手牌，往左冒
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
print(li)
li = [3,2,4,1,5,7,9,6,8]
print(li)
insert_sort(li)