对快排的一点认识

最近需要用到快排，所以想用手写一下快排的代码，快排的原理是相当清楚的，每次找到一个pivot(基准值)，小于等于该值的放到数组的左半边，大于该值的放到数组的右半边，这样就能把原数组一分为二，减小了数组的规模，再对子数组做相同的处理，直到子问题的数组规模变为单个数组时，该数组就已经是有序的了。说写就写，下面是我一开始写出来的代码。

import numpy as np
import sys

def QuickSort(a, ll, rr):
    if ll >= rr: return
    pos = did(a, ll, rr)
    QuickSort(a, ll, pos-1)
    QuickSort(a, pos+1, rr)

def did(a, ll, rr):
    piv = a[ll]
    t  = ll
    while ll < rr:
        while ll < rr and a[ll] <= piv: ll += 1
        while ll < rr and a[rr] > piv: rr -= 1
        a[ll], a[rr] = a[rr], a[ll]
    a[ll], a[t] = a[t], a[ll]
    return ll

def test():
    for i in range(5):
        lst = np.random.randint(0, 100, 10)
        print(lst)
        QuickSort(lst, 0, len(lst)-1)
        print(lst)

if __name__ == '__main__':
    test()

一开始运行的结果如下图所示

quicksort-1.png

仔细观察发现结果是错误的。于是开始找问题究竟出在哪了。
找啊找，找啊找，就是想不出来。最后手工模拟了一遍之后发现问题的根源。
导致发生错误的地方就是下面两行代码的顺序问题

while ll < rr and a[ll] <= piv: ll += 1
while ll < rr and a[rr] > piv: rr -= 1

调换一下这两行的顺序之后，运行结果如下图，看来结果是正确的。

quicksort-2.png

为什么这两行代码的顺序会影响程序的正确性呢？

手动模拟一下快排就会发现，我们取最左边的数组元素作为pivot，并且在每一轮迭代后，把a[t]和a[ll]的值进行交换，这里t值为原始的ll。每一轮迭代结束的条件是ll == rr，而我们交换a[t]和a[ll]的必要条件是a[ll] <= a[t]，按照最原始的写法，如果第一个while循环结束时满足ll == rr，那么第二个循环不会执行，此时不能确保a[ll] <= a[t]。调换两行while代码的顺序后，如果第一个while循环结束的时ll==rr，则ll的值为上一轮循环结束时的值，满足a[ll] <= a[t],如果第一个while循环结束时的条件式为a[rr] <= piv，则第二个while循环可以执行，不会出现错误。

我所理解的就是这样的。所以如果我们每次把数组区间的最后一个元素作为pivot的话，应该先执行检测a[ll]值的那个while循环。

以前没有注意到这些细节问题，这次踩了个坑，所以学习算法只了解了原理是不够的，还要多动手实现一些算法，才能真正掌握。