Python实现快速排序

'''
快速排序原理：对于给定的一组序列，选择一个基准数，通过一论排序后，将原序列分为两部分，
使得前面的比后面的小，然后再依次对前后进行拆分并排序，递归该过程，直到序列中所有数据均有序为止。
算法过程如下：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 arrays

if __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(n2)理想的情况下，每次划分将问题分解为两个规模为n/2的子问题，递归求解两个规模的子问题， 所需时间为2T(n/2) 合并：因为是原地排序，合并不需要时间复杂度，所以时间复杂度为 O(nlogn) 空间复杂度：O(logn)

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