快速排序：快快排思路：取一个元素p（第一个元素），使元素p归位；列表被p分成两部分，左边都比p小，右边都比p大；递归完成排序。

import randomfrom timewrap import *import copyimport syssys.setrecursionlimit(100000)def partition(li, left, right):    # ri = random.randint(left, right)    # li[left], li[ri] = li[ri], li[left]    tmp = li[left]    while left < right:        while left < right and li[right] >= tmp:            right -= 1        li[left] = li[right]        while left < right and li[left] <= tmp:            left += 1        li[right] = li[left]    li[left] = tmp    return leftdef _quick_sort(li, left, right):    if left < right:    # 至少有两个元素        mid = partition(li, left, right)        _quick_sort(li, left, mid-1)        _quick_sort(li, mid+1, right)@cal_timedef quick_sort(li):    return _quick_sort(li, 0, len(li)-1)@cal_timedef sys_sort(li):    li.sort()li = list(range(10000))random.shuffle(li)#sys_sort(li1)quick_sort(li)

 

堆排序建立堆得到堆顶元素，为最大元素去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。堆顶元素为第二大元素。重复步骤3，直到堆变空。

from timewrap import *import randomdef _sift(li, low, high):    """    :param li:    :param low: 堆根节点的位置    :param high: 堆最有一个节点的位置    :return:    """    i = low  # 父亲的位置    j = 2 * i + 1  # 孩子的位置    tmp = li[low]  # 原省长    while j <= high:        if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子存在并且右孩子更大            j += 1        if tmp < li[j]:  # 如果原省长比孩子小            li[i] = li[j]  # 把孩子向上移动一层            i = j            j = 2 * i + 1        else:            li[i] = tmp  # 省长放到对应的位置上(干部)            break    else:        li[i] = tmp  # 省长放到对应的位置上(村民/叶子节点)def sift(li, low, high):    """    :param li:    :param low: 堆根节点的位置    :param high: 堆最有一个节点的位置    :return:    """    i = low         # 父亲的位置    j = 2 * i + 1   # 孩子的位置    tmp = li[low]   # 原省长    while j <= high:        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子存在并且右孩子更大            j += 1        if tmp < li[j]: # 如果原省长比孩子小            li[i] = li[j]  # 把孩子向上移动一层            i = j            j = 2 * i + 1        else:            break    li[i] = tmp@cal_timedef heap_sort(li):    n = len(li)    # 1. 建堆    for i in range(n//2-1, -1, -1):        sift(li, i, n-1)    # 2. 挨个出数    for j in range(n-1, -1, -1):    # j表示堆最后一个元素的位置        li[0], li[j] = li[j], li[0]        # 堆的大小少了一个元素 （j-1）        sift(li, 0, j-1)li = list(range(10000))random.shuffle(li)heap_sort(li)print(li)# li=[2,9,7,8,5,0,1,6,4,3]# sift(li, 0, len(li)-1)# print(li)

 

归并排序假设现在的列表分两段有序，如何将其合成为一个有序列表这种操作称为一次归并。分解：将列表越分越小，直至分成一个元素。终止条件：一个元素是有序的。合并：将两个有序列表归并，列表越来越大。

import randomfrom timewrap import *import copyimport sysdef merge(li, low, mid, high):    i = low    j = mid + 1    ltmp = []    while i <= mid and j <= high:        if li[i] < li[j]:            ltmp.append(li[i])            i += 1        else:            ltmp.append(li[j])            j += 1    while i <= mid:        ltmp.append(li[i])        i += 1    while j <= high:        ltmp.append(li[j])        j += 1    li[low:high+1] = ltmpdef _merge_sort(li, low, high):    if low < high:  # 至少两个元素        mid = (low + high) // 2        _merge_sort(li, low, mid)        _merge_sort(li, mid+1, high)        merge(li, low, mid, high)        print(li[low:high+1])def merge_sort(li):    return _merge_sort(li, 0, len(li)-1)li = list(range(16))random.shuffle(li)print(li)merge_sort(li)print(li)