python排序算法(一)

def bubble_sort(lyst):
    for i in range(len(lyst)):
        for j in range(len(lyst)-1, i, -1):
            if lyst[j] < lyst[j-1]:
                lyst[j], lyst[j-1] = lyst[j-1], lyst[j]

def select_sort(lyst):
    for i in range(len(lyst)):
        minIndex = i
        for j in range(i+1,len(lyst)):
            if lyst[j] < lyst[minIndex]:
                minIndex = j
        lyst[i], lyst[minIndex] = lyst[minIndex], lyst[i]

def insert_sort(lyst):
    for i in range(1, len(lyst)):
        j, temp = i-1, lyst[i]
        while j >= 0 and lyst[j] > temp:
            lyst[j+1], j = lyst[j], j-1
        lyst[j+1] = temp

def shell_sort(lyst):
    gap = len(lyst)//2
    while gap:
        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
        gap //= 2

def merge_sort(lyst):
    if len(lyst) <= 1:
        return lyst
    left = merge_sort(lyst[:len(lyst)//2])
    right = merge_sort(lyst[len(lyst)//2:])
    l = r = index = 0
    while l<len(left) and r<len(right):
        if left[l] <= right[r]:
            lyst[index], l = left[l], l+1
        else:
            lyst[index], r = right[r], r+1
        index += 1
    lyst[index:] = left[l:] if l<len(left) else right[r:]
    return lyst

def quick_sort(lyst):
    def quick_helper1(lyst, left, right):
        """快慢指针确定分界，其中slow表示下区间的右界, left,right为左闭右开区间"""
        if left >= right-1:
            return
        pivot = left
        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]
        quick_helper1(lyst,left, slow)
        quick_helper1(lyst, slow+1, right)

    def quick_helper2(lyst, left, right):
        """左右指针确定分界，其中l或l-1表示下区间的右界, left,right为左闭右开区间"""
        if left >= right-1:
            return
        pivot = left
        l, r = left+1, right-1
        while l < r:
            if lyst[l] <= lyst[pivot]:
                l += 1
            elif lyst[r] > lyst[pivot]:
                r -= 1
            else:
                lyst[l], lyst[r] = lyst[r], lyst[l]
                l += 1
                r -= 1
        if lyst[l] > lyst[pivot]:#确定实际分界
            l -= 1
        lyst[pivot], lyst[l] = lyst[l], lyst[pivot]
        quick_helper2(lyst,left,l)
        quick_helper2(lyst, l+1, right)

    quick_helper1(lyst, 0, len(lyst))

def heap_sort(lyst):
    def max_heapify(lyst, i, length):
        l, r = 2*i+1, 2*i+2
        maxIndex = i
        if l<length and lyst[maxIndex]<lyst[l]:
            maxIndex = l
        if r<length and lyst[maxIndex]<lyst[r]:
            maxIndex = r
        if maxIndex != i:
            lyst[i], lyst[maxIndex] = lyst[maxIndex], lyst[i]
            max_heapify(lyst, maxIndex, length)

    def build_heap(lyst):
        for i in range(len(lyst)//2,-1,-1):
            max_heapify(lyst, i, len(lyst))

    build_heap(lyst)
    for i in range(len(lyst)-1,0,-1):
        lyst[0], lyst[i] = lyst[i], lyst[0]
        max_heapify(lyst, 0, i)

def count_sort(lyst):
    maxValue = max(lyst)
    minValue = min(lyst)
    counts = [0]*(maxValue - minValue + 1)
    for num in lyst:
        counts[num-minValue] += 1#将取值归一到 min--max之间
    cur = 0
    for index, count in enumerate(counts):
        if not count:
            continue
        lyst[cur:cur+count] = [index+minValue]*count
        cur += count

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, merge_sort, quick_sort, heap_sort, count_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.221662282943726
Time used by select_sort: 3.8268022537231445
Time used by insert_sort: 4.620638608932495
Time used by shell_sort: 0.057811737060546875
Time used by merge_sort: 0.054853200912475586
Time used by quick_sort: 0.028922557830810547
Time used by heap_sort: 0.07084536552429199
Time used by count_sort: 0.004951953887939453
"""