理解快速排序算法

一月 18, 2018  /  Pp

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

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

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

image.png

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

就是说,快速排序的主要步骤就是:找X + 跟X比大小排列?

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

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

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

image.png

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

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

image.png

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

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

image.png

image.png

image.png

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

image.png

image.png

image.png

image.png

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

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

image.png

image.png

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

image.png

image.png

考虑到这一点,我们就可以意识到,要做的是把一开始找的标杆放到应有的位置上,即最后一个<=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的数替换为“█”,则有:

image.png

↓↓

image.png

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

image.png

是不是清晰许多?

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

image.png

完整代码如下:

def quicksort(data):     #快速排序
    stone = data[0]
    i = 1
    j = len(data)-1
    if len(data) > 1:     #分为len(data) >2len(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

完结撒花~