'''快速排序原理：对于给定的一组序列，选择一个基准数，通过一论排序后，将原序列分为两部分，使得前面的比后面的小，然后再依次对前后进行拆分并排序，递归该过程，直到序列中所有数据均有序为止。算法过程如下：1.拆分：将序列拆分成2个非空子序列2.递归求解：通过递归调用快速分别对2个子序列进行排序3.合并：把排序好的2个子序列进行合并例如数组：{49,38,65,97,76,13,27,49}，具体排序过程如下：第一次排序过程：初始化：[49,38,65,97,76,13,27,49]第1次交换：[27,38,65,97,76,13,49,49]第2次交换：[27,38,49,97,76,13,65,49]第3次交换：[27,38,13,97,76,49,65,49]第4次交换：[27,38,13,49,76,97,65,49]整个排序过程：初始化：[49,38,65,97,76,13,27,49]第1次排序后：[27 38 13] 49 [76 97 65 49]第2次排序后：[13] 27 [38] 49 [49 65] 76 [97]第3次排序后：13 27 38 49 49 [65] 76 97最后排序结果：13 27 38 49 49 65 76 97'''#代码实现def quick_sort(arrays,left,right):    if left>=right:        return list    key=arrays[left]    low=left    high=right    while left<right:        while left < right and arrays[right]>= key:            right-=1        arrays[left]=arrays[right]        while left < right and arrays[left]<=key:            left+=1        arrays[right]=arrays[left]    arrays[right]=key    quick_sort(arrays,low,left-1)    quick_sort(arrays,left+1,high)    return arraysif __name__=="__main__":    arrays=[49,38,65,97,76,13,27,49]    print("排序前：" + str(arrays))    print("排序后："+str(quick_sort(arrays,0,len(arrays)-1)))排序结果如下：

时间复杂度：最坏的情况下，每次划分将问题分解后，基准元素的一侧没有元素，其中一侧为规模为n-1的子问题， 递归求解该子问题，所需时间为递归求解该子问题，所需时间为T(n-1),合并：因为是原地排序，合并不需要时间复杂度，所以时间复杂度为 O(n²)理想的情况下，每次划分将问题分解为两个规模为n/2的子问题，递归求解两个规模的子问题， 所需时间为2T(n/2) 合并：因为是原地排序，合并不需要时间复杂度，所以时间复杂度为 O(nlogn) 空间复杂度：O(logn)

欢迎大家关注我的微信公众号