Python带你快速了解快速排序！

快速排序作为我们在数据结构面试中经常看到的一种算法，对于我们的理解和掌握是非常重要的。下面我将通过一个简单的分步说明图和代码说明，带大家快速了解它。

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort）。

通过one-pass sorting将待排序的数据分成独立的两部分，其中一部分的所有数据都小于另一部分的所有数据，然后按照这种方法对两部分数据进行快速排序，整体排序过程可以是递归的，使整个数据成为一个有序的序列。

步骤为：

1，从数列中挑出一个元素，称为"基准"（pivot），

2.重新排序序列，所有小于参考值的元素都放在参考值的前面，所有大于参考值的元素都放在参考值的后面（相同的数字可以去任何一边）。本次划分结束后，基准处于序列的中间。这称为分区操作。

3.递归排序小于参考值的元素子序列和大于参考值的元素子序列。

import random
def quick_sort(alist,start,end):
    if start>end:
        return
    # 如果前值大于后值则排序停止   此时low指针和high指针重合
    low = start
    high = end
 
    middle = alist[start]
    # middle 是我们开始时定的基准的值而low和high表示指针的位置
 
    while low < high:
        while low < high and alist[high] >= middle:
            high -= 1
        alist[low] = alist[high]
        while low < high and alist[low] <= middle:
            low += 1
        alist[high] = alist[low]
        # 当退出循环的时候，证明low指针指向的数据有大于基准middle的，所以讲这个大于middle的数和high的位置进行交换
    alist[low] = middle
    # 推出循环之后，low和high的位置重合，此时这个重合的位置就是middle元素应该在的位置，此时将middle放置此处，一次大循环结束
    quick_sort(alist, start, low-1)
    quick_sort(alist, low+1,end)
list1=[]
# 用生成随机数的方法去验证我们的排序算法
for i in range(30):
    list1.append(random.randint(1, 300))
quick_sort(list1, 0, len(list1)-1)
print(list1)

时间复杂度

最优时间复杂度：O(nlogn)

最坏时间复杂度：O(n2)

稳定性：不稳定

从一开始，快速排序平均花费 O(n log n) 时间并不明显。但是不难观察到，分区操作，数组的元素会经过每一次循环，使用O(n)的时间。在使用联合的版本中，这个操作也是 O(n)。

在最好的情况下，每次我们运行分区时，我们都会将一个序列分成两个几乎相等的部分。

这意味着每个递归调用处理数组大小的一半。

因此，我们只需要在达到大小为 1 的数组之前进行 log n 次嵌套调用。

这个意思就是调用树的深度是O(log n)。

但是在同一层级的两个程序调用中，原序列的同一部分没有被处理；因此，程序调用的每个层次总共只需要 O(n) 时间（每个调用都有一些共同的额外成本，但由于每个层次只有 O(n) 次调用，所以这些调用在 O(n) 系数中求和）。

结果是这个算法仅需使用O(n log n)时间。