# -*- coding: utf-8 -*-

import random


list_input = [random.randint(0, 5000) for _ in xrange(10)]


def qsort(input_list):
    if len(input_list) <= 1:
        return input_list
    middle_number = input_list[len(input_list) / 2]
    left = [i for i in input_list if i < middle_number]
    middle = [i for i in input_list if i == middle_number]
    right = [i for i in input_list if i > middle_number]
    return qsort(left) + middle + qsort(right)


# 进阶： 排序分割, 把一个数组分为, 大于k\小于k\等于k的三个部分
def qsort2(input_list, k):
    if len(input_list) <= 1:
        return input_list
    middle_number = k
    left = [i for i in input_list if i < middle_number]
    middle = [i for i in input_list if i == middle_number]
    right = [i for i in input_list if i > middle_number]
    return qsort(left), middle, qsort(right)


if __name__ == "__main__":
    print qsort(list_input)
    list_input = [2, 2, 1, 2, 3, 3, 3, 4, 5, 6]
    print qsort2(list_input, 3)