基于比较类型排序性能比较

from memory_profiler import profile


def quick_sort(l: list):
    length = len(l)
    if length <= 1:
        return l
    p_index = random.randint(0, length - 1)
    p = l[p_index]
    less = -1  # 小于n的区域
    more = length  # 大于n的区域
    index = 0  # 当前索引位置
    while index < more:
        if l[index] < p:
            less += 1  # 小于n区域右移1
            l[index], l[less] = l[less], l[index]
            index += 1  # 当前位置加1
        elif l[index] > p:
            more -= 1  # 大于n区域左移1，当前位置不变
            l[index], l[more] = l[more], l[index]
        else:
            index += 1  # 当前位置加1
    return quick_sort(l[0:less + 1]) + l[less + 1:more] + quick_sort(l[more:])


def quick_sort1(l: list):
    if len(l) <= 1:
        return l
    left, mid, right = [], [], []
    # base_index=random.randint(0,len(l)-1) # 随机选取分组对象，可以最大限度使得当前排序的时间复杂度接近O(nlogn)
    base = l[0]
    for i in l:
        if i < base:
            left.append(i)
        elif i > base:
            right.append(i)
        else:
            mid.append(i)
    return quick_sort(left) + mid + quick_sort(right)


def bubble_sort(l: list):
    for i in range(len(l)):
        for j in range(i + 1, len(l)):
            if l[i] > l[j]:
                l[i], l[j] = l[j], l[i]
    return l


import heapq


def heapify(arr: list, index: int, heap_size: int):
    '''
    堆放，使根节点值最大或最小
    考察index位置的值能否往下沉，较大的孩子如果大于父，父节点往下沉，较大孩子上去，循环向下走，直到走不下去
    heap_size：堆大小，可以灵活使用，控制下沉深度
    '''
    left = index * 2 + 1
    while left < heap_size:
        # 获取两个孩子中最大孩子的索引
        largest = left + 1 if left + 1 < heap_size and arr[left + 1] > arr[left] else left
        # 获取最大孩子跟当前头中较大的值的索引
        largest = largest if arr[largest] > arr[index] else index
        # 比较确认孩子的值是否更大,
        if largest == index:
            break
        #  如果头比孩子小就交换值，继续向下比较
        arr[index], arr[largest] = arr[largest], arr[index]
        index = largest
        left = index * 2 + 1
    return arr


def heapinsert(arr: list, index: int):
    '''
    堆插入
    大根堆：当前节点值跟父节点的值比较，如果当前位置值大于父位置值，则当前位置值跟父位置的值交换，从而实现大根堆
    index:当前位置节点，
    (index-1)//2:父位置节点
    '''
    while index and arr[index] > arr[(index - 1) // 2]:
        arr[index], arr[(index - 1) // 2] = arr[(index - 1) // 2], arr[index]
        index = (index - 1) // 2
    return arr


def heap_sort(l: list):
    print(l)
    h = []
    while l:
        # heapq.heapify(l)
        # h.append(l.pop(0))
        h.append(heapq.heappop(l))
    return h


def heap_sort1(l: list):
    if l is None or len(l) < 2:
        return
    # case_1、先插入数据后排序,可以应对某些动态场景(O(N*logN));一个一个数给
    # for i in range(len(l)):
    #     heapinsert(l, i)

    # case_2、直接heapify排序(O(N*logN));一次给全部数
    i = len(l) - 1
    for _ in range(len(l)):
        heapify(l, i, len(l))
        i -= 1
    heap_size = len(l)
    heap_size -= 1
    l[0], l[heap_size] = l[heap_size], l[0]
    while heap_size > 0:
        heapify(l, 0, heap_size)
        heap_size -= 1
        l[0], l[heap_size] = l[heap_size], l[0]
    return l


@profile(precision=4, stream=open('quick_sort.log', 'w+'))
def test_quick_sort(list_length):
    l = [random.randint(0, 1000) for _ in range(list_length)]
    s = time.time()
    res = quick_sort(l)
    e = time.time()
    print(e - s)


@profile(precision=4, stream=open('quick_sort1.log', 'w+'))
def test_quick_sort1(list_length):
    l = [random.randint(0, 1000) for _ in range(list_length)]
    s = time.time()
    res = quick_sort1(l)
    e = time.time()
    print(e - s)


@profile(precision=4, stream=open('bubble_sort.log', 'w+'))
def test_bubble_sort(list_length):
    l = [random.randint(0, 1000) for _ in range(list_length)]
    s = time.time()
    res = bubble_sort(l)
    e = time.time()
    print(e - s)


@profile(precision=4, stream=open('heap_sort.log', 'w+'))
def test_heap_sort(list_length):
    l = [random.randint(0, 1000) for _ in range(list_length)]
    s = time.time()
    res = heap_sort(l)
    print(res)
    e = time.time()
    print(e - s)


@profile(precision=4, stream=open('heap_sort1.log', 'w+'))
def test_heap_sort1(list_length):
    l = [random.randint(0, 1000) for _ in range(list_length)]
    s = time.time()
    res = heap_sort1(l)
    print(res)
    e = time.time()
    print(e - s)


@profile(precision=4, stream=open('sort.log', 'w+'))
def test_sort(list_length):
    l = [random.randint(0, 1000) for _ in range(list_length)]
    s = time.time()
    l.sort()
    # print(l)
    e = time.time()
    print(e - s)


list_length = 100
# test_quick_sort(list_length)
# test_quick_sort1(list_length)
# test_bubble_sort(list_length)
test_heap_sort(list_length)
# test_heap_sort1(list_length)
# test_sort(list_length)