记录几个常见的排序算法

常见的排序有：快速排序、冒泡排序、希尔排序、选择排序、插入排序、归并排序

冒泡排序：

def bubble_sort(li):
    n = len(li)
    # 遍历列表，让下标从0取得列表右边倒数对二个位置
    # 一趟冒泡，让最大的数移动到最右边
    
    for j in range(n-1):
        flag = 0
        for i in range(n-1-j):
            # 拿当前位置的数与下一个数进行比较
            if li[i] > li[i+1]:
                li[i],li[i+1] = li[i+1],li[i]
                flag += 1
        # 内层循环如果循环一次后，flag没有变化的话，说明列表已经是有序的
        if flag == 0:
            break

if __name__ = '__main__':
    l = [1,4,6,8,5]
    bubble(l)
    print(l)

插入排序：

def insert_sort(li):
    n = len(li)
    # 认为第一个数是有序的，从后面取一个数，倒着往前遍历，插入到前面的有序队列中
    for j in range(1, n):
        for i in range(j, 0, -1):
            if li[i] <li[i-1]:
                li[i],li[i-1] = li[i-1],li[i]
            else:
                break
if __name__ = '__main__':
    l = [1,3,7,9,4,3]
    insert_sort(l)
    print(l)

选择排序：

def select_sort(li):
    n = len(li)
    # 记录0位置的数据，认为0位置的数据最小
    temp = 0
    # 依次跟后面的数据进行比较
    
    for i in range(1, n):
        if li[i] < li[temp]:
        # 把最小数的位置记起来
        temp = i 
    # 循环结束时，temp指向的是最小数的位置
    li[temp],li[0] = li[0],li[temp]

希尔排序：

def shell_sort(li):
    n = len(li)
    # 定义步长
    gap = n//2
    # 让步长由大变小，最后变为1
    while gap >= 1:
        # 按照步长，把数据分成两半，遍历后一半数据
        for i in range(gap, n):
            # 让当前位置跟减去一个步长的下标数进行比较
            while (i - gap) >= 0:
                if li[i]<li[i-gap]:
                    li[i],li[i-gap] = li[i-gap], li[i]
                i -= gap
        gap //= 2
        

快速排序：

def quink_sort(li, start, end):
    # 定义两个变量记录下标位置
    low = start
    high = end
    #　定义一个用来比较的数字
    mind = li[low]
    while low < high:
        while low < high and li[high] >= mind:
            high -= 1
        li[low] = li[high]
        while low < high and li[low] < mind:
            low += 1
        li[high] = li[low]
    li[low] = mind
    quink_sort(li, start, low-1)
    quink_sort(li, low+1, end)