算法导论第二章

插入排序

• 最小复杂度 $O(n)$
• 最大复杂度 $O(n^2)$
• 平均复杂度 $O(n^2)$

def Insertion_Sort_Asce(lis):
    for i in range(1,len(lis)):
        j = i
        key = lis[j]
        while j > 0 and key < lis[j-1]:
            lis[j] = lis[j-1]
            j = j - 1
        lis[j] = key
    return lis

def Insertion_Sort_Desc(lis):
    for i in range(1,len(lis)):
        j = i
        key = lis[j]
        while j > 0 and key > lis[j-1]:
            lis[j] = lis[j-1]
            j = j - 1
        lis[j] = key
    return lis

归并排序

• 最小复杂度 $O(n \log n)$
• 最大复杂度 $O(n \log n)$
• 平均复杂度 $O(n \log n)$

def Merge(lis1, lis2):
    if lis1 == []:
        return lis2
    if lis2 == []:
        return lis1
    if lis1[0] <= lis2[0]:
        return [lis1[0]] + Merge(lis1[1:], lis2)
    else:
        return [lis2[0]] + Merge(lis1, lis2[1:])

def Merge_Sort(lis):
    if len(lis) > 1:
        q = len(lis)/2
        return Merge(Merge_Sort(lis[:q]), Merge_Sort(lis[q:]))
    else:
        return lis