[数据结构与算法]简单快速排序 （python）

def q_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return q_sort(less) + [pivot] + q_sort(greater)

时间复杂度：

1. 最优：O(nlogn) 每一次取到的元素都刚好平分整个数组, 栈的高度为O(logn), 而每层需要的时间是O(n), 总时间 O(logn) * O(n) = O(nlogn)
2. 最差：O(n^2) 每一次取到的元素就是数组中最小/最大的
3. 如果每次随机地选择一个元素作为pivot，那么平均时间为O(nlogn)

import random
def q_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        idx = random.randrange(0, len(arr))
        pivot = arr[idx]
        less = [i for i in arr[:idx] if i <= pivot] + [i for i in arr[idx+1:] if i <= pivot]
        greater = [i for i in arr[:idx] if i > pivot] + [i for i in arr[idx+1:] if i > pivot]
        return q_sort(less) + [pivot] + q_sort(greater)