#!/bin/env python
#
def quicksort(lists):
    if len(lists) <= 1:
        return lists
    l_length = len(lists)-1
    start = lists[0]
    end = lists[l_length]
    base = end
    pos = l_length
    for i,n in enumerate(lists):
        if i < pos and n < base:
            lists[pos] = n
            lists[i] = base
            pos = i
    return quicksort(lists[0:int(pos)]) + [base] + quicksort(lists[int(pos):])

def quicksort2(list1,start,end):
    if start >= end:
        return
    mid = list1[start]
    low = start
    hight = end
    print(hight,'===')
    while low < hight:
        while low < hight and list1[hight] >= mid:
            hight -= 1
        list1[low] = list1[hight]
        while low < hight and list1[low] < mid:
            low += 1
        list1[hight] = list1[low]
        list1[low] = mid
        quicksort2(list1, start, low-1)
        quicksort2(list1, low+1, end)
            
def quicksort3(nums):
    if len(nums) <= 1:
        return nums

    # 左子数组
    less = []
    # 右子数组
    greater = []
    # 基准数
    base = nums.pop()

    # 对原数组进行划分
    for x in nums:
        if x < base:
            less.append(x)
        else:
            greater.append(x)

    # 递归调用
    return quicksort(less) + [base] + quicksort(greater)
            
def main():
    testlists = [5,4,1,3]        
    print quicksort(testlists)
    #print quicksort2(testlists,0,3)

if __name__ == '__main__':
    main()