插入排序 选择排序 冒泡排序

def swap(li,a,b):    t = li[a]    li[a] = li[b]    li[b] = tdef bubble_sort(li):    for i in range(len(li)-1,0,-1):        for j in range(0,i):            if li[j]>li[j+1]:                swap(li,j,j+1)def selection_sort(li):    for i in range(0,len(li)):        for j in range(i,len(li)):            if li[j]
    
     li[j+1]:                swap(li,j,j+1)            else:                break
    

Shell sort

def shell_sort(li):    h = 1    while h < len(li)//3 :h = 3*h +1    while h:        insertion_sort(li,h)        h = h//3

快速排序

def __quick_sort(li,left,right):    def quick_sort_once(l,r):        p = li[l]        pindex = l+1        for i in range(l+1,r+1):            if li[i] < p:                swap(li,i,pindex)                pindex+=1        swap(li,pindex-1,l)        return pindex-1    if right-left<1:        return    else:        pindex = quick_sort_once(left,right)        __quick_sort(li,left,pindex-1)        __quick_sort(li,pindex+1,right)

归并排序

def merge_sort(li): # 从下往上递归     def merge(left,right):        result = []        i,j = 0,0        while i

堆排序

def heap_sort(li):    def max_index(a,b,lastIndex):        if b > lastIndex or li[a]>li[b]:            return a         else:            return b    def swap_if_a_lt_b(a,b):        if li[a] > li[b]:            return -1        else:            swap(li,a,b)            return b    #max heap    def fix(i,lastIndex=len(li)-1):        l = 2*i + 1        if  l > lastIndex:            return         r = 2*i +2        m = max_index(l,r,lastIndex)        result = swap_if_a_lt_b(i,m)        if result > 0:            fix(result,lastIndex)    # create max heap:    length = len(li)//2    for x in range(length,-1,-1):        fix(x)    #sort     for j in range(len(li)-1,-1,-1):        swap(li,j,0)        fix(0,j-1)

Radix sort

def radix_sort(li):    bucket = []    for i in range(0,10):        bucket.append([])    temp = li    def find_max(li):        m = li[0]        for x in li:            if x>m:m=x        return m    def digit_count(d):        c = 0        while d:            d = d//10            c += 1        return c    def insert(n):        d = 10**(n-1)        for x in temp:            bucket[(x//d)%10].append(x)    def popitem():        nonlocal temp        temp = []        for x in bucket:            while x:                temp.append(x.pop(0))    m = find_max(li)    d = digit_count(m)    for i in range(1,d+1):        insert(i)        popitem()    return temp

测试样例

import randoml1,l2,l3,l4=[],[],[],[]for x in range(1000):    l1.append(random.randint(0,1000))    l2.append(random.randint(0,1000))    l3.append(random.randint(0,1000))    l4.append(random.randint(0,1000))def validate(li):    p = li[0]    for x in range(1,len(li)):        if li[x]