Python快速排序算法

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

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

快速排序的流程如图 1 所示(以升序排序为例)。
快速排序
图 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 数组。