排序算法 #algorithm

排序算法.md

快排

• 第3行: 判断列表长度是否小于等于1， 如果小于等于1，直接返回列表
• 第4行：返回递归函数拼接的列表，[lt for lt in L[1:] if lt <= L[0]] 列表推导表达式，返回一个比 L[0] 小的列表，[ge for ge in L[1:] if ge >= L[0]], 返回一个比L[0] 大的列表， 再加上L[0] 就构成完整的列表

#coding:utf-8
def qsort(L):
    if len(L) <= 1: return L
    return qsort([lt for lt in L[1:] if lt < L[0]]) + L[0:1]+ \
    qsort([ge for ge in L[1:] if ge >= L[0]])

iList = [3,14,2,12,9,33,99,35]

print qsort(iList)

in-place(就地) 快排

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low]
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list