快速排序

选择一个元素作为pivot, 所有元素根据与pivot的关系, 分成三部分:
small, big, same.
small与big需要用递归继续排序.
边界条件: 当序列长度 <= 1时, 直接返回序列.

时间复杂度

平均时间复杂度为O(n * log(n))

Python 代码

def quicksort(A):
    if len(A) < 2:
        return A
    p = A[len(A)//2]
    small = []
    big = []
    same = []
    for e in A:
        if e < p:
            small.append(e)
        elif e > p:
            big.append(e)
        else:
            same.append(e)

    return quicksort(small) + same + quicksort(big)

n = int(input())
A = list(map(int, input().split()))

for e in quicksort(A):
    print(e, end=" ")