堆排序

def heap_sort(ary) :
    n = len(ary)
    first = int(n/2-1)      #最后一个非叶子节点
    for start in range(first,-1,-1) :       #构造大根堆：最后一个非叶子节点 -> 根节点
        max_heapify(ary,start,n-1)
    for end in range(n-1,0,-1):     #堆排，将大根堆转换成有序数组
        ary[end],ary[0] = ary[0],ary[end]       #最大的交换到末尾，调整交换后的其余节点
        max_heapify(ary,0,end-1)
    return ary


#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置，end为调整边界
def max_heapify(ary,start,end):
    root = start
    while True :
        child = root*2 +1       #调整节点的子节点
        if child > end : break
        if child+1 <= end and ary[child] < ary[child+1] :
            child = child+1     #取较大的子节点
        if ary[root] < ary[child] :     #较大的子节点成为父节点
            ary[root],ary[child] = ary[child],ary[root] #交换
            root = child
        else :
            break

快速排序(simple)

# 快排
def quickSort(arr):
    if len(arr)<=1:return arr
    low,pi,high = partition(arr)
    return quickSort(low)+[pi]+quickSort(high)

# 分区
def partition(arr):
    pi , arr = arr[0],arr[1:]
    low = [x for x in arr if x<=pi]
    high = [x for x in arr if x>pi]
    return low,pi,high

快速排序(regular)

def quick_sort(ary):
    return qsort(ary,0,len(ary)-1)

def qsort(ary,left,right):
    #快排函数，ary为待排序数组，left为待排序的左边界，right为右边界
    if left >= right : return ary
    key = ary[left]     #取最左边的为基准数
    lp = left           #左指针
    rp = right          #右指针
    while lp < rp :
        while ary[rp] >= key and lp < rp :
            rp -= 1
        while ary[lp] <= key and lp < rp :
            lp += 1
        ary[lp],ary[rp] = ary[rp],ary[lp]
    ary[left],ary[lp] = ary[lp],ary[left]
    qsort(ary,left,lp-1)
    qsort(ary,rp+1,right)
    return ary

归并排序

# MergeSort
def mergeSort(arr):
    mid = len(arr)/2
    left ,right = arr[:mid],arr[mid:]
    if len(left)>1:
        left = mergeSort(left)
    if len(right)>1:
        right = mergeSort(right)
    res = []
    while left and right:
        if left[-1]>=right[-1]:
            res.append(left.pop())
        else:
            res.append(right.pop())
    res.reverse()
    return (left or right)+res

Shell排序

def shell_sort(ary):
    n = len(ary)
    gap = round(n/2)       #初始步长 , 用round四舍五入取整
    while gap > 0 :
        for i in range(gap,n):        #每一列进行插入排序 , 从gap 到 n-1
            temp = ary[i]
            j = i
            while ( j >= gap and ary[j-gap] > temp ):    #插入排序
                ary[j] = ary[j-gap]
                j = j - gap
            ary[j] = temp
        gap = round(gap/2)                     #重新设置步长
    return ary

插入排序

def insert_sort(lists):
    # 插入排序
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists

选择排序

def select_sort(ary):
    n = len(ary)
    for i in range(0,n):
        min = i                             #最小元素下标标记
        for j in range(i+1,n):
            if ary[j] < ary[min] :
                min = j                     #找到最小值的下标
        ary[min],ary[i] = ary[i],ary[min]   #交换两者
    return ary

冒泡排序

def bubble_sort(arry):
    n = len(arry)                   #获得数组的长度
    for i in range(n):
        for j in range(1,n-i):
            if  arry[j-1] > arry[j] :       #如果前者比后者大
                arry[j-1],arry[j] = arry[j],arry[j-1]      #则交换两者
    return arry