Python快速排序算法

快速排序的思想是：取数组中的一个数作为基准值，把所有小于基准值的数都放在它的一侧，再把所有大于基准值的数都放在它的另一侧。随后，对基准值左右两侧的数组分别进行快速排序。由此可以看出，快速排序的整个排序过程也是递归进行的。

快速排序的平均时间复杂度是 O(nlgn)，最好情况下的时间复杂度是 O(nlgn)。最坏情况下，快速排序的时间复杂度可能退化成 O(n2)，但这种情况很少见。它的空间复杂度是 O(nlgn)。它是一个不稳定的排序算法。如果使用得当，快速排序的速度可以达到归并排序和堆排序的数倍，所以快速排序是一种极其常用的算法。

以升序排序为例，快速排序的流程如下：

图 1：快速排序

一般情况下，我们取数组的第一个数作为基准进行快速排序。在第一步中，基准数为 5。可以看出，在第二行的数组中，比 5 小的元素：3、4、1、2，都被置于 5 的左侧，而比 5 大的元素则被置于 5 的右侧。这时，元素 5 在有序数组中的位置就确定了。

第三行中，我们再取左右两个无序数组的第一个数 3 和 6，分别作为它们的基准数，然后再次对数组进行分拆。分拆结束之后，3 和 6 在有序数组中的位置也确定了。

接下来，继续处理分拆出来的 4 个子数组：[1,2]、[4]、[]、[8,7]。其中，一个子数组只剩一个数，一个为空。这意味着 [4] 与 [] 已经完成了对自己的快速排序。而其他的两个子数组则需继续处理。全部处理完毕后，我们将得到一个完整的有序数组。

可以看出，快速排序也是通过这样的分治思想来排序的。关于它的分治思想我们之后会继续讲解。 

快速排序代码（基础版）

nums = [5,3,6,4,1,2,8,7]
def QuickSort(num):
    if len(num) <= 1: #边界条件
        return num
    key = num[0] #取数组的第一个数为基准数
    llist,rlist,mlist = [],[],[key] #定义空列表，分别存储小于/大于/等于基准数的元素
    for i in range(1,len(num)): #遍历数组，把元素归类到3个列表中
        if num[i] > key:
            rlist.append(num[i])
        elif num[i] < key:
            llist.append(num[i])
        else:
            mlist.append(num[i])
    return QuickSort(llist)+mlist+QuickSort(rlist) #对左右子列表快排，拼接3个列表并返回
print(QuickSort(nums))

运行程序，输出结果为：

[1,2,3,4,5,6,7,8]

在 QuickSort( ) 函数中，首先是边界条件：如果传入函数的列表长度小于等于 1，那么这一段列表必定是有序的，可以直接返回。如果不满足边界条件，则继续执行函数。先用 key 存储基准值，再定义 3 个列表存储小于基准数的元素 llist，大于基准数的元素 rlist 和等于基准数的元素 mlist。由于接下来 for 循环的范围不包括列表中的第一个数，所以对 mlist 初始化时，多加一个初始元素 key。

接下来的 for 循环把数组内的元素分别归入 3 个列表中。随后，再次调用 QuickSort( ) 函数，对 llist 和 rlist 进行排序。这样，llist 和 rlist 就是有序的了，而 mlist 内的元素刚好处于它们中间的连接部分。所以，排序完成后，把 llist、mlist、rlist 按顺序拼接到一起并输出。

这是实现快速排序的一种方式。但是，这样实现快速排序需要额外开辟空间给用于归类的列表。并且，相似的思路应用于其他的编程语言时效率较低。那么，该如何优化这个算法，使得数组可以原地排序呢？

我们需要优化的是把基准值移动到正确位置的那一部分代码。具体的移动流程如下：

我们用一个变量存储基准值。然后，再使用两个指针，一个从左往右遍历，一个从右往左遍历。开始遍历时，可以把基准值在数组中的位置，也就是第一个元素，视作一个没有元素的空位。

1) 如图 2 所示，移动右边的指针，一直到指针指向的元素小于基准值为止。

图 2：优化快速排序第一步

2) 如图 3 所示，把右边的指针指向的值 2 赋给左边的指针指向的位置。这时候，原来 2 所在的位置实际上是空出来的空位，空位在图 2 中用浅色字体表示。

图 3：优化快速排序第二步

 3) 如图 4 所示，移动左边的指针，等到它指向了一个大于等于基准值的数再停下。类似地，把左边的指针指向的值赋给右边的指针指向的位置。左边指针指向的位置成为空位。

图 4：优化快速排序第三步

 4) 重复以上步骤，不断地交替移动左边的指针和右边的指针，并赋值，如图 5 所示。

图 5：重复相似步骤

 5) 如图 6 所示，当左指针和右指针重合时，所有必要的移动都已经完成。左指针和右指针共同指向的位置就是基准值在有序数组中的位置。它的值大于它左侧的所有元素，并小于等于它右侧的所有元素（如果有相等的元素出现）。剩余的步骤为递归地排序左右子数组，直到全部数组排序完毕。

 图 6：当前范围内移动完成

快速排序代码（“原地”版）：

nums = [5,3,6,4,1,2,8,7]
def QSort(left,right):　　　　　　 #子数组第一个元素和最后一个元素在原数组中的位置
    if(left >= right):　　　　　　　#边界条件
        return
    l,r,key = left,right,nums[left]　#初始化左指针，右指针和基准值
    while(l < r):　　　　　　　　　 #调整元素位置
        while l < r and nums[r] >= key:
            r -= 1
        nums[l] = nums[r]
        while l < r and nums[l] < key:
            l += 1
        nums[r] = nums[l]
    nums[l] = key　　　　　　　　　 #把基准值赋给左指针和右指针共同指向的位置
    QSort(left,l-1)　　　　　　　　 #左侧数组排序
    QSort(l+1,right)　　　　　　　　#右侧数组排序
QSort(0,len(nums)-1)
print(nums)

运行程序，输出结果为：

[1,2,3,4,5,6,7,8]

这段代码没有采用直接将数组传入函数的方法，而是把子数组第一个和最后一个元素的位置传入函数中，从而确定循环范围。边界条件仍然不变：只有当子数组的长度（right-left+1）大于 1 时才继续递归。左指针 l 和右指针 r 初始化为第一个元素的下标和最后一个元素的下标，变量 key 用于存储基准值。

随后，while 循环就实现了前面图 2 ～图 6 展示的调整元素位置的过程。最后把两个子数组中间的位置赋值为 key，再对两个子数组分别排序。在函数外部，先调用 QSort( ) 函数对 nums 数组进行排序，再输出 nums 数组。