Python实现快速排序

一、快速排序简介

快速排序(Quick Sort)是一种效率很高的排序算法，是对冒泡排序的一种改进排序算法。

快速排序首先任意选取一个数据(通常选待排序列表中的第一个数)作为基准数据，将待排序列表中的数据分割成独立的两部分，所有比基准数据小的数都放到它左边，所有比基准数据大的数都放到它右边，此时基准数据排序完成，第一轮快速排序完成。然后再按此方法对两部分的数据分别进行快速排序，整个排序过程可以递归进行，直到被分割的数据只有一个或零个时，递归结束，列表排序完成。

快速排序的名字起得简单直接，因为这种排序算法速度快，效率高，是处理大数据最快的排序算法之一。

二、快速排序原理

快速排序的原理如下：

1. 从待排序列表中选取一个基准数据(通常选取第一个数据)。

2. 将待排序列表中所有比基准数据小的元素都放到基准数据左边，所有比基准数据大的元素都放到基准数据右边(升序排列，降序反之)。用基准数据进行分割操作后，基准数据的位置就是它最终排序完成的位置，第一轮排序完成。

3. 递归地对左右两个部分的数据进行快速排序。即在每个子列表中，选取基准，分割数据。直到被分割的数据只有一个或零个时，列表排序完成。

以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。

要进行升序排列，则每轮排序都将比基准数据小的数据放在左边，比基准数据大的数据放在右边。

1. 从待排序列表中任意选一个数据作为基准数据 mid_data，然后设置两个游标 left 和 right，分别指向列表的起始数据和末尾数据。将游标right的数据与基准数据比较，如果大于或等于基准数据，则right往左移动。基准数据为10，21大于10，right左移。

2. 当游标right的数据小于基准数据时，right停止移动，将游标right指向的数据赋值给游标left。然后将游标left的数据与基准数据比较，如果小于基准数据，则left往右移动。right移动到5时小于10，停止移动并将5赋值给left，left开始右移。

3. 当游标left的数据大于或等于基准数据时，left停止移动，将游标left指向的数据赋值给游标right。然后将游标right的数据与基准数据比较，如果大于或等于基准数据，则right往左移动。left移动到17时大于10，停止移动并将17赋值给right，right开始左移。

4. 重复步骤2，right移动到7时小于10，停止移动并将7赋值给left，left开始右移。

5. 重复步骤3，left移动到50时大于10，停止移动并将50赋值给right，right开始左移。

6. 当left与right相遇时，移动结束，将基准数据10赋值给相遇的位置，此时第一轮排序完成，列表被基准数据分割成了两个子列表，基准数据10的位置就是排序完成时的位置。

7. 递归地对分割的两个子列表进行相同的操作。以左表为例，取第一个数据5作为基准数据，设置两个游标left和right指向子表的起始和末尾，将游标right的数据与基准数据比较，如果大于或等于基准数据，则right往左移动。

8. 左表中只有两个数据，经过一次移动，left和right就相等了，移动结束，左表排序完成。对右表也使用相同方法进行递归，这里就不再赘述了。

9. 继续进行多轮递归排序，每一轮当子表只有一个或零个数据时(left>=right)，递归结束。排序结果如下图。

三、Python实现快速排序

# coding=utf-8
def quick_sort(array, start, end):
    if start >= end:
        return
    mid_data, left, right = array[start], start, end
    while left < right:
        while array[right] >= mid_data and left < right:
            right -= 1
        array[left] = array[right]
        while array[left] < mid_data and left < right:
            left += 1
        array[right] = array[left]
    array[left] = mid_data
    quick_sort(array, start, left-1)
    quick_sort(array, left+1, end)


if __name__ == '__main__':
    array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
    quick_sort(array, 0, len(array)-1)
    print(array)

运行结果：

[5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

在代码中，先将列表中的第一个数据作为基准数据mid_data，设置两个游标left和right分别标记待排序列表起始和末尾的数据。然后按照上面分析的步骤，left和right两个游标交替向中间移动，当left与right相遇时，将mid_data赋值给相遇位置的索引。此时完成了分割，mid_data左边子表中的数据都小于基准数据，右边子表中的数据都大于基准数据，第一轮排序完成。然后递归对左右两个子列表执行相同操作，递归结束的条件就是列表的长度小于2时(start>=end)，此时直接返回。

快速排序除了需要传入待排序列表以外，还需要传入排序的开始索引和结束索引，也就是说快速排序可以指定排序列表中的部分数据，在递归的时候就是排序部分数据。

快速排序也可以使用非递归的方式实现，在非递归实现时，代码思路不变，但必须借助栈或队列，代码会稍微长一点。

四、快速排序的时间复杂度和稳定性

1. 时间复杂度

在快速排序中，最坏的情况是元素列表的初始状态是完全逆序排列的，这使得每次分割所得的子表中一个为空表，另一个的长度为原表的长度减1，所以需要进行 n 轮分割，每一轮需要进行 n/2 次比较。时间复杂度为 T(n)=n(n-1)/2 ，再乘每次操作的步骤数(常数，不影响大O记法)，所以快速排序的时间复杂度为 O(n^2) 。

与时间复杂度是 O(n^2) 的其他排序算法相比，为什么快速排序的效率会比其他排序算法高呢？因为时间复杂度计算的是最坏情况的时间复杂度，但最坏的情况并不常见。快速排序的最优时间复杂度是 Ο(nlogn) ，很容易改变取基准数据的方法避免最坏情况的发生(如“三者值取中”)，去接近最优时间复杂度。

2. 稳定性

在快速排序中，每轮排序会将数据与基准数据进行比较和分割。如果有相等的数据，可以自己决定将相等的数据放在左边还是右边(上面的代码是右边)，不会影响排序结果。

在快速排序的实现过程中，有两个游标从列表的两边向中间移动，游标right向左移动的过程中，如果数据小于基准数据，则会将数据赋值给left游标。在这个过程中，如果有相等的数据，相对位置很可能会发生变化，如 [10, 5, 5] 。所以快速排序是一种不稳定的排序算法。