理解快速排序算法

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。根据@张小牛 的文章快速排序(Quick Sort)详解，证明最优的排序算法，其时间复杂度可为O(nlogn)，对应的空间复杂度可为O(n)。快速排序可实现理论最优效率，这可能是快速排序比较重要的原因吧。

我们基于Python学习写一下快速排序吧。

先给定一个长度为10的列表data = [5, 4, 7, 8, 2, 7, 8, 5, 6, 3]，如下：

初始列表

有了一个列表，看起来会直观多了吧，但是我们想放着不管。快速排序的主旨很简单：找一个标杆数，称为X，然后根据X把数组的数分堆，小于X的全放左边，大于X的全放右边，就可以啦。对于实际情况呢，我们还需要考虑等于X的情况，我将其与小于归为一起，即数组排列后，形成“小于等于X” + “大于X”两部分。

就是说，快速排序的主要步骤就是：找X + 跟X比大小排列？

你可能会疑惑，只是按“比X大或比X小”排列数组，怎么能得到完整的排序呢。一次排列几乎不可能排好，但我们可以将排了一次的数组上，切分为“小于等于X”和“大于X”两块，再对这两块分别再找标杆数X'和X''，接着再分别排序。最后组合再一起，就得到了排列了两次的数组，其顺序肯定更接近完美序列。那么我们继续这么“切分→找标杆数→排列”操作下去呢？在此例中，由于每一分堆总小于右侧的分堆，而大于左侧的分堆，同时每个分堆内部已排好序，因此整个序列排序完成。

以上这种操作叫做“递归”，可以对数组不断地切分并采用同样的排列模式进行排列，直到递归条件不再满足，则停止递归。在这里，我们选择切分后数组的长度大小，作为递归的条件，细节在后面详述。

我们不妨先试着试验一下，找X，然后将数组跟X比大小排列。我没有研究哪一个当标杆好，不如就选第一个数字吧。

选择第一个数字为“标杆数”

下面我们就要依据“标杆数”，也就是数字“5”（其序数为0），对其余部分进行分堆了。我们想分为“<=5”与“>5”的两部分，并使前者位于左侧，后者位于右侧，操作步骤如下：

1. 命名左侧序数为 i，初始 i = 1；命名右侧序数为 j，初始 j = len(data)-1（即最后一位）。

初始化i、j

2. 让j开始移动并进行判断：

• 若j所在的数字<=5，则让i开始向右移动，直到i所在的数字>5，接着交换data中i, j所对应的数字，即:

data[i], data[j] = data[j], data[i]

• 若j所在数字>5，则忽略，继续向左移动。

3. 当 j == i 时，意味着交换结束，列表除了首位的“标杆数”，其余部分分为<=5和>5两堆，那么我们还应该把“5”放到这两堆中间，让列表看上去更有序。即：

data[0], data[j] = date[j], data[0]

注意：如果j此时不在列表中间呢，比如由于数据特殊，j最终停在在首、尾处呢？

不能交换 可以交换

考虑到这一点，我们就可以意识到，要做的是把一开始找的标杆放到应有的位置上，即最后一个<=5的数的位置。因此，我们在交换前加一个判断：

if data[j] <= data[0]:
    data[0], data[j] = data[j], data[0]

4. 结束操作，返回此时的data。


容易看到，由于我让j的移动占主动性，j先找到一个<=5的数后，i才能开始行动找>2的数。那么当j、i会，请问j最终会停在<=5还是>5的数字上呢？

答案是：对于这里给出的data，j总是会停在<=5的数字上，或者说对于len(data)>5的data，j与i总是相遇在最右的“<=标杆数”的位置上（仔细想一想~）。
这样做是为了便于data[j]与data[0]交换，所以让j先行；如果让i先行，那么相反的，i、j通常相遇在最左的“>标杆数”的位置上，这样不利于data[i]与data[0]交换。
对于len(data) == 1 or len(data) == 2的两种例外情况，留给读者思考。伪代码如下：

if len(data) == 2:
    if data[j] <= data[0]:
            data[0], data[j] = data[j], data[0]
        return quicksort(data[left_part]) + quicksort(data[right_part])

if len(data) == 1:
    return data

以上部分讲的是单次排序的（啰嗦）细节，整个快速排序是若干次单次排序的递归，下面讲解一下递归部分：

首先简化模型，我们把不直观的“数字比大小”转换为直观的“图形排序”，将data中的“标杆数5”及<=5的数替换为“☻”，将>5的数替换为“█”，则有：

接着，用上述的i，j排序规则操作一遍之后，得到：

是不是清晰许多？

进行递归，我们要做的就是把分大小排序的data拆分为两个data，分界线即为“标杆数”，然后分别对两个拆分data排序，直至抵达递归的回归条件（len(data) <= 1即终止）。
对示例列表进行快速排序的原理如下：

完整代码如下：

def quicksort(data):     #快速排序
    stone = data[0]
    i = 1
    j = len(data)-1
    if len(data) > 1:     #分为len(data) >2和len(data) == 2两种情况，可合并
        while j > i:
            if data[j] <= stone:
                if data[i] > stone:
                    data[j], data[i] = data[i], data[j]
                else:
                    i += 1
            else:
                j -= 1
        if data[j] <= stone:     #当len(data) == 2时只执行此部分
            data[0], data[j] = data[j], data[0]
        return quicksort(data[:j]) + quicksort(data[j:])
    else:     #回归条件，len(data) <= 1
        return data

完结撒花~
以上 .