常用algorithm及其Python实现，,冒泡排序def bu

冒泡排序

def bubble_sort(li):    for i in range(len(li)-1): # i表示第几趟        exchange = False        for j in range(len(li)-i-1): # j表示图中的箭头            if li[j] > li[j+1]:                li[j], li[j+1] = li[j+1], li[j]                exchange = True        if not exchange:            return

选择排序

def select_sort(li):    for i in range(len(li)-1):        # 第i趟开始时 无序区：li[i:]        # 找无序区最小值，保存最小值的位置        min_pos = i     # min_pos保存最小值的位置        for j in range(i+1, len(li)):            if li[j] < li[min_pos]:                min_pos = j        li[min_pos], li[i] = li[i], li[min_pos]

插入排序

def insert_sort(li):    for i in range(1, len(li)): # i是摸到的牌的下标        tmp = li[i]        j = i - 1 # j是手里最后一张牌的下标        # 两个终止条件：j小于0表示tmp是最小的 顺序不要乱        while j >= 0 and li[j] > tmp:              li[j+1] = li[j]            j -= 1        # for j in range(i-1, -1, -1):        #     if li[j] > tmp:        #         li[j+1] = li[j]        #     else:        #         break        li[j+1] = tmp

快速排序

def partition(li, left, right):    randi = random.randint(left, right)    li[randi], li[left] = li[left], li[randi]    tmp = li[left]    while left < right:        while left < right and li[right] >= tmp:            right -= 1        li[left] = li[right]        while left < right and li[left] <= tmp:            left += 1        li[right] = li[left]    li[left] = tmp    return leftdef _quick_sort(li, left, right):    if left < right:    # 至少两个元素        mid = partition(li, left, right)        _quick_sort(li, left, mid - 1)        _quick_sort(li, mid + 1, right)@cal_timedef quick_sort(li):    return _quick_sort(li, 0, len(li)-1)li = list(range(10000, 0, -1))quick_sort(li)

堆排序

def sift(li, low, high):    tmp = li[low]    i = low    j = 2 * i + 1    while j <= high: # 退出条件2：当前i位置是叶子结点，j位置超过了high        # j 指向更大的孩子        if j + 1 <= high and li[j+1] > li[j]:            j = j + 1 # 如果右孩子存在并且更大，j指向右孩子        if tmp < li[j]:            li[i] = li[j]            i = j            j = 2 * i + 1        else:       # 退出条件1：tmp的值大于两个孩子的值            break    li[i] = tmp@cal_timedef heap_sort(li):    # 1. 建堆    n = len(li)    for i in range(n//2-1, -1, -1):        # i 是建堆时要调整的子树的根的下标        sift(li, i, n-1)    # 2.挨个出数    for i in range(n-1, -1, -1): #i表示当前的high值 也表示棋子的位置        li[i], li[0] = li[0], li[i]        # 现在堆的范围 0~i-1        sift(li, 0, i-1)

归并排序

def merge(li, low, mid, high):    i = low    j = mid + 1    ltmp = []    while i <= mid and j <= high:        if li[i] < li[j]:            ltmp.append(li[i])            i += 1        else:            ltmp.append(li[j])            j += 1    while i <= mid:        ltmp.append(li[i])        i += 1    while j <= high:        ltmp.append(li[j])        j += 1    # for k in range(low, high+1):    #     li[k] = ltmp[k-low]    li[low:high+1] = ltmpdef merge_sort(li, low, high):    if low < high:        mid = (low + high) // 2        merge_sort(li, low, mid)        merge_sort(li, mid+1, high)        merge(li, low, mid, high)# li = list(range(10000))# random.shuffle(li)# merge_sort(li, 0, len(li)-1)# print(li)li = [10,4,6,3,8,2,5,7]merge_sort(li, 0, len(li)-1)

总结

常用algorithm及其Python实现