常用排序

1. 冒泡

def pp(list):
    n = len(list)
    for i in range(n):
        for j in range(n-i-1):
            if list[j] > list[j+1]:
                list[j], list[j+1] = list[j+1],list[j]

2. 快排

def sort(arr):
    if len(arr) < 2:
        return arr
    flag = arr[0]
    big = [x for x in arr if x > flag]
    same = [x for x in arr if x == flag]
    small = [x for x in arr if x < flag]
    return sort(big) + same + sort(small)

3. 插入

def insertSort(list):
    n = len(list)
    for i in range(n):
        tmp = list[i]
        j = i - 1
        print "out", list, j, tmp
        while j >= 0 and list[j] > tmp:
            # print list
            list[j+1] = list[j] #换值
            print list,j
            # list[j],list[j+1] = list[j+1], list[j]
            j = j - 1
        arr[j+1] = tmp #换值
        print "fin", list,tmp

4. 选择

def selectSort(arr):
    n = len(arr)
    for i in range(n):
        tmp = i
        for j in range(i+1, n):
            if arr[j] < arr[tmp]:
                tmp = j
        arr[i], arr[tmp] = arr[tmp], arr[i] 

5. 归并（分治）
   随机找个数，分比他的大，小的；分到单个数；在合并（merge函数是重点）

def merge_sort(alist):
    """
    递归分治序列
    :param alist:
    :return:
    """
    if len(alist) <= 1:
        return alist
    num = len(alist)//2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    return merge(left, right)  # 合并
 
def merge(left, right):
    """
    合并操作
    :param left:
    :param right:
    :return:
    """
 
    l, r = 0, 0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:  # 筛选排序将left与right最小元素按序加入新序列
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

6. 拓扑 （图，之前存在依赖关系）
   有向无环图，利用bfs|dfs进行处理，删除入度为0，查他周围，选择入度为0，处理。

   
   image.png