快速排序

• O(nlogn)，如果每次选的枢纽值都是边缘，实际是O(n^2)了；可以考虑取列表索引的首、尾、中间值取三个值的中间值为枢纽值，对于比较有序的列表排序时就能常常取到合适的枢纽值
• 相对归并排序，好处是不必另外开辟空间

def quick_sort(lst):
    sort_help(lst, 0, len(lst)-1)

def sort_help(lst, start, end):
    if start < end:
        split_point = partition(lst, start, end)

        sort_help(lst, start, split_point - 1)
        sort_help(lst, split_point + 1, end)        


def partition(lst, start, end):
    point_value = lst[start]
    left = start + 1
    right = end

    while left < right:
        while lst[left] < point_value:
            left += 1
        while lst[right] > point_value:
            right -=1
        if left < right:
            lst[left], lst[right] = lst[right], lst[left]
    lst[start], lst[right] = lst[right], lst[start]
    return right

lst = [54,26,93,17,77,31,44,55,20]
quick_sort(lst)
print lst

归并排序

def merge_sort(num_list):
    '归并排序'
    length = len(num_list)
    if length < 2:
        return num_list
    
    n = length / 2
    a_list = merge_sort(num_list[:n])
    b_list = merge_sort(num_list[n:])

    sort_num_list = []
    while a_list and b_list:
        num = min(a_list[0], b_list[0])
        if num == a_list[0]:
            del a_list[0]
        else:
            del b_list[0]
        sort_num_list.append(num)
    sort_num_list.extend(a_list)
    sort_num_list.extend(b_list)
    return sort_num_list

num_list = [3, 1, 34, 5, 0, 9]
print merge_sort(num_list)