排序问题：冒泡排序，选择排序，插入排序

什么是列表排序

• 排序：将一组“无序”的记录序列调整为“有序”的记录序列

• 列表排序：将无序列表变为有序列表

  ​ 输入：列表

  ​ 输出：有序列表

• 升序与降序

• 内置排序函数sort()

  ​ sort是在源列表排序，sortted是创建一个新的排序后的列表，源列表不变。

常见排序算法介绍

排序算法分析

冒泡排序(Bubble Sort)

• 列表每相邻的数，如果前面比后面大，则交换这两个数

• 一趟排序完成后，则无序区减少一个数，有序区增加一个数

• 冒泡排序一般要进行多趟

• 代码关键点：趟，无序区范围

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
        print(li)
    if not exchange:
        return

li = [9,8,7,1,2,3,4,5,6]
bubble_sort(li)
 

选择排序(select_sort)

• 一趟排序记录最小的数，放到第一个位置
• 在一趟排序记录记录列表无序区最小的数，放到第二个位置
• 算法关键点：有序区和无序区，无序区最小数的位置

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)

插入排序（insert_sort）

• 初始时手里(有序区)只有一张牌
• 每次(从无序区)摸一张牌，插入到手里已有牌的正确位置

def insert_sort(arry):   #排序之前的列表
    for idx in range(1, len(arry)):
        j = idx
        while j > 0 and arry[j] < arry[j-1]:
            (arry[j-1], arry[j]) =(arry[j], arry[j-1])
            j -= 1
    return arry

arry = [1,2,5,7,6,9,8,4,3]
print(insert_sort(arry))