排序算法之快速排序

最好时间复杂度：
最坏时间复杂度：

排序思想：
每次循环会选择一个key，从数组尾处循环找比key小元素将其放在i位置，从数组头找比key大的位置放在j位置

def QuickSort(arr,low,high):
    i = low
    j = high
    #循环跳出条件
    if i >= j :
        return arr
    #注意key = arr[i]一定是在跳出条件后面
    key = arr[i]
    #每一次while循环都是把数组分为两部分，左面比key小，右面比key大
    while i < j:
        while i < j and arr[j] >= key:
            j -= 1
        arr[i] = arr[j]
        while i < j and arr[i] <= key:
            i += 1
        arr[i] = key
    QuickSort(arr,low,i - 1)
    QuickSort(arr,j+1,high)
    return arr