一、算法复杂度

二、算法流程

1、寻找一个基准值pivot，将小于基准的放到基准的左边，大于基准的放在右边，这个操作叫做partition；

2、递归的将基准左边和右边的子序列重复上面的步骤；

三、代码实现

import copy
def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp

def partition(arr, left_idx, right_idx):
    #小于基准值的放在左边，大于基准值的放在右边，返回基准的当前索引；
    pivot = left_idx
    index = pivot + 1
    for i in range(index, right_idx + 1):
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index += 1
    swap(arr, pivot, index - 1)
    return index - 1

def quick_sort_recur(arr, left, right):
    #递归排列子序列;
    if left < right:
        pivot_idx = partition(arr, left, right)
        quick_sort_recur(arr, left, pivot_idx - 1)
        quick_sort_recur(arr, pivot_idx + 1, right)
    return arr
    
def quick_sort(s):
    arr = copy.deepcopy(s)
    return quick_sort_recur(arr, 0, len(arr) - 1)

#测试结果
test = [3, 5, 4, 7, 2]
print(quick_sort(test)) #[2, 3, 4, 5, 7]