快速排序的python实现

入门写法：

写法一：简单，但是扩展性不强

# 快排：设定一个分界值(一般取第一个)，大于分界去右边，小于分界去左边，递归重复这个过程
# ref=5 i=1 j=5     5 3 7 6 4  j从后往前找 第一个比5小的是4 交换 4 3 7 6 5
# i=1 j=5 从前往后找 第一个比5大的是7 交换 4 3 5 6 7
# i=2 j=5 这时发现左边的都比5大 右边的都比5小 然后递归处理左右两遍
 
def qsort(a):
    if(len(a)<=1):
        return a
 
    ref=a[0]
    a.remove(a[0]) #remove操作是为了方便理解，移除列表中某个值的 第一个 匹配项。
    #print(a)
    l,r=[],[]
    for i in range(0,len(a)):
        if(a[i]>=ref):
            r.append(a[i])
        else:
            l.append(a[i])
    # print("l=",l,"ref=",ref,"r=",r) # 需要数组演化情况时运行这行，注释是为了精确运算时间
    return qsort(l)+[ref]+qsort(r)

写法二：推荐，可以迁移到其他算法中

注意：pivot是比较的起点，partition函数会让pivot左边都小于pivot，右边都大于pivot。这里便于理解，直接将数组第一个元素作为pivot

#原始快排