概念

快速排序（Quicksort),又称为交换排序，通过一趟排序将要排序的数据分割为独立的两部分。假设要排序的列表是A[0]…A[N-1]，首先任意选取一个数据（通常选用列表的第一个数）作为基准数据，一般我们都选择第一个数作为基准数据，然后将所有比它小的数都放到它的左边，所有比它大的数都放到它的右边，这个过程称为快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变化。

算法步骤

  1. 设置两个low、high，排序开始的时候：low=0，high=N-1
  2. 以第一个列表元素作为基准数据，赋值给mid，即mid=A[0]
  3. 从high开始向前搜索，即由后开始向前搜索(high–),找到第一个小于mid的值A[high],将A[high]和A[low]的值交换
  4. 从low开始向后搜索，即向前开始向后搜索(low++),找到大于mid的A[low],将A[low]和A[high]的值交换。
  5. 重复第3、4步，直到low=high；

时间复杂度

  • 最优时间复杂度：O(nlogn) #每次分成两半，要分logn次，再乘遍历的n次
  • 最坏时间复杂度：O(n2) #每次只分出一个元素出来，要分n次，再乘遍历的n次
  • 稳定性：不稳定

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def quick_sort(alist,start,end):
    """
    :param alist:
    :return:alist.sort
    快速排序首先要选择一个基准，将其他数据与这个基准比较，比它大的放右边，比它小的放左边，循环这个过程，完成排序
    定义两个指针，一个low一个high,
    开始是high先做比较，如果high对应的元素比基准大就不懂，high--，如果比基准小，则与low对应的元素交换，然后low++
    直到low==high说明一趟快速排序已经完成，再将基准添加到序列中
    上面已经完成一次快速排序，再将左序列和右序列进行递归，注意设置一个出口，即可完成整个遍历
    以alist = [5,1,3,2,8,7,6,4]为例
    以alist = [4,1,3,2,8,7,6,4]为例
    """
    # 递归的出口
    if start >= end:
        return
    mid = alist[start]  # 定义基准 5
    low = start  # 左指针
    high = end  # 右指针 7
    # 判断high是不是大于mid,大于的话就不用交换，之间high--，直到小于的时候进行交换
    while low <high:
        while alist[high] >= mid and high > low:  #7>0
            high -=1
        alist[low] = alist[high]
        #判断low是不是小于mid, 小于的话就不用交换，之间low++，直到大于的时候进行交换
        while alist[low] < mid and high>low:
            low += 1
        alist[high] = alist[low]
    alist[low] = mid
    quick_sort(alist,0,low-1)
    quick_sort(alist,low+1,end)
    return alist

总结

主要是两个指针的交替变化，可以用while循环来执行，判断high是不是大于mid,大于的话就不用交换，之间high–，直到小于的时候进行交换；判断low是不是小于mid, 小于的话就不用交换，之间low++，直到大于的时候进行交换；最后再加上基准，这样就完成一次快速排序，之后再从外面用一个while循环，里面用递归思想不断对左序列和右序列进行操作，记得写一个出口，start >= end，这样快速排序算法就结束了。