python排序算法(二)

def radix_sort_iteration(lyst):
    minNum = min(lyst)
    n = len(str(max(lyst)-minNum))#计算归一化后的最大位数，即最大值与最小值差的位数
    for bit in range(n):
        buckets = {i:[] for i in range(10)}#以10为基数，设置10个桶
        for num in lyst:
            index = int((num-minNum)/(10**bit))%10#计算桶标号
            buckets[index].append(num)
        lyst[:] = [num for i in range(10) for num in buckets[i]]

def radix_sort_recursion(lyst):
    def radix_helper(lyst, bit, n):
        if bit >= n:
            return
        minNum = min(lyst)
        buckets = {i:[] for i in range(10)}#以10为基数，设置10个桶
        for num in lyst:
            index = int((num-minNum)/(10**bit))%10#计算桶标号
            buckets[index].append(num)
        lyst[:] = [num for i in range(10) for num in buckets[i]]
        radix_helper(lyst, bit+1, n)

    n = len(str(max(lyst)-min(lyst)))#计算归一化后的最大位数，即最大值与最小值差的位数
    radix_helper(lyst, 0, n)

def bucket_sort(lyst):
    n = max(10, len(lyst)//10)#设置至少10个、最多len/10个桶，此时平均每个桶中10个元素
    minNum = min(lyst)
    d = (max(lyst) - minNum+1)/n
    buckets = {i:[] for i in range(n)}
    for num in lyst:
        index = int((num-minNum)/d)##取整得到桶标号
        buckets[index].append(num)
    lyst[:] = [num for i in range(n) for num in sorted(buckets[i])]

def shell_sort_recursion(lyst):
    def shell_helper(lyst, gap):
        if not gap:
            return
        for i in range(gap, len(lyst)):
            j, temp = i-gap, lyst[i]
            while j >= 0 and lyst[j] > temp:
                lyst[j+gap], j = lyst[j], j-gap
            lyst[j+gap] = temp
        shell_helper(lyst, gap//2)

    gap = len(lyst)//2
    shell_helper(lyst, gap)

def merge_sort_iteration(lyst):
    length = len(lyst)
    size = 1
    while size<length:#从步长1开始归并，直至
        temp = lyst[:]
        for i in range((length//(2*size))+1):###当前步长下，需要分多少归并区间
            start = i*2*size ##每一块归并区间的起点
            l, r = start, start+size ##归并区间的左右起点
            index = start
            while l < start+size and r < min(start+2*size, length):#对左右子区间进行归并
                if temp[l] <= temp[r]:
                    lyst[index], l = temp[l], l+1
                else:
                    lyst[index], r = temp[r], r+1
                index += 1
            lyst[index:min(start+2*size, length)] = temp[l:start+size] if l < start+size  else temp[r:min(start+2*size, length)]#拼接剩余的部分
        size *= 2

def quick_sort_iteration(lyst):
    unSort = [(0, len(lyst))]#定义待排序区间列表
    while unSort:
        left, right = unSort.pop()#取出一个待排序区间：[left, right)
        pivot = slow = left
        for fast in range(left+1, right):
            if lyst[fast] <= lyst[pivot]:
                slow += 1
                lyst[fast], lyst[slow] = lyst[slow], lyst[fast]
        lyst[pivot], lyst[slow] = lyst[slow], lyst[pivot]
        if slow-left > 1:
            unSort.append((left, slow))
        if right - slow-1 > 1:
            unSort.append((slow+1, right))

if __name__ == '__main__':
    lyst = list(range(1,10001))
    from random import shuffle
    shuffle(lyst)
    import time
    sorts = [bubble_sort, 
            select_sort, 
            insert_sort, 
            shell_sort_iteration, shell_sort_recursion, 
            merge_sort_recursion, merge_sort_iteration, 
            quick_sort_recursion, quick_sort_iteration,
            heap_sort, 
            count_sort, 
            radix_sort_iteration, radix_sort_recursion, 
            bucket_sort]
    for sort in sorts:
        start = time.time()
        sort(lyst[:]) 
        print(f"Time used by {sort.__name__}:", time.time()-start)

"""
Time used by bubble_sort: 10.429074764251709
Time used by select_sort: 3.9225099086761475
Time used by insert_sort: 4.868975877761841
Time used by shell_sort_iteration: 0.07384204864501953
Time used by shell_sort_recursion: 0.0568084716796875
Time used by merge_sort_recursion: 0.049866437911987305
Time used by merge_sort_iteration: 0.07679462432861328
Time used by quick_sort_recursion: 0.02994680404663086
Time used by quick_sort_iteration: 0.032884836196899414
Time used by heap_sort: 0.07779192924499512
Time used by count_sort: 0.004985332489013672
Time used by radix_sort_iteration: 0.028949260711669922
Time used by radix_sort_recursion: 0.02690863609313965
Time used by bucket_sort: 0.006009101867675781
"""