'''
快速排序是分而治之（Divide and Conquer）思想的一个典型应用。
简单说，就是用递归来实现。

给定一个无序列表 [5,3,2,7,1,9,6,10],

选择列表的第一个元素5, 用这个元素把列表里的元素分隔成两部分l1 & l3，这个操作只是分隔，不对分隔出来的子列表排序。
如果l1 & l3 都是有序的，那么 l1,l2,l3拼接起来就是原始列表的有序副本。

这个例子分隔出来如下：
前面的子列表l1： [3,2,1]
中间的数l2：    [5]
后面的子列表l3：[7,9,6,10]

接下来，分别获取l1 & l3的第一个元素作为分隔符，对l1 & l3递归调用分隔：
             [3,2,1],       [5],             [7,9,6,10]
    [2,1]  [3] None  ，  [5]              [6] [7] [9,10]
只要某个子列表里的元素大到2个或以上，就对这个自列表递归调用函数：
[1] [2] None [3] None  ， [5]         [6] [7] None [9] [10]

最后函数的调用栈依次返回，把每个子列表拼接起来，就得到原始无序列表的有序版本了：
[1,2,3,5,6,7,9,10]


python实现起来应该比较简单，因为python可以在列表里加上expression, 类似这个效果：
[x for x in l1 if x > 2]

Q:能否不用第一个元素，而是用中间的某个元素作为分隔？
A:完全可以，但是如果列表是无序的那么就没优势。
因为这个列表本身是无序的，那随便选择哪个元素都是一样的，而选择第一个元素的话，代码写起来清晰简单。
但是如果列表是有序的，如果这时候选择第一个元素，就会导致l1(或者l2，取决于排序方向)始终为空，递归的调用栈高度就会很长。


假如原始列表里有重复的元素，那么这个算法没有去保证重复元素的相对位置不变，所以这个算法是‘不稳定’的。

'''


def quick_sort(obj):
    len_obj = len(obj)
    if len_obj <= 1:
        return obj
    else:
        l2 = obj[0]
        # 坑1.因为元素可能有重复的，所以不能漏掉了=的情况
        # 坑2. obj[1:len_obj] 要用冒号才是切片，不能用逗号 [1, len_obj]
        # 坑3. obj[1:len_obj] 的范围包含开始index但不包含结束的index，是 1 ~ len_obj -1, 所以定义的时候不能用[1:len_obj-1]。
        l1 = [i for i in obj[1:len_obj] if i <= l2]
        l3 = [i for i in obj[1:len_obj] if i > l2]
        # 坑4.list和int不能直接相加，要把l2转换成list类型:[l2]
        return quick_sort(l1) + [l2] + quick_sort(l3)


l1 = [7,3,4,2,6,5,1,9,8,10,6,6,6,6]
print(quick_sort(l1))


