---

3-2 快速排序讨论

---

目录

小节	位置
3.2.1	基础问题-分块操作
3.2.2	经典快速排序问题
3.2.3	荷兰国旗问题
3.2.4	利用荷兰国旗问题改进快
3.2.5	快速排序再改进

3.2.1 基础问题-分块操作

分块问题（Partition 问题）：
给定一个数组arr，和一个数num，请把小于 num的数放在数组的左边，大于等于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)。

• 解决思路_1：
  设立一个游标，该游标可以从左向右逐渐移动，移动的条件为，将数组中小于num的数，不断的插入到游标的位置，然后游标右移。
  这样，游标的左侧区域就逐渐扩张，相当于顶着游标在往右移动。
  最终，当所有元素都考察过之后，游标左侧区域的数，一定是小于num，游标右侧的数大于等于num。

def Swap(a, i, j):
    try:
        a[i], a[j] = a[j], a[i]
    except:
        print(i, j)

def Partition_1(a):

    N = len(a)
    # 我们现在假设待比较的num是数组最后的元素，即N-1位置的元素
    # L 就是我们的游标，在这里，我们设置游标L指向 小于等于num区域 的最后一个数的位置
    # 由于最开始的时候，左侧区域是没有数的，所以游标初始值是-1
    key, L = N-1, -1
    base = a[key]
    # 因为 N-1位置的值，被我们当作比较的基准，所以只用遍历前N-1个数
    for i in range(0, N-1):
        # 这里的意思是，如果i位置的数，小于基准数
        # 就将i位置的数，与游标L右侧紧挨着的数交换位置，同时游标L右移一位，左侧区域扩张一位
        if a[i] < base:
            Swap(a, i, L+1)
            L+=1
    # for循环遍历完之后, 数组 0-L位置上的数都是小于base的数
    # 最后将key位置的基准数num与游标右侧L+1位置的数字交换，
    # 因为while循环结束之后，游标右侧的数一定是大于等于base的
    # 所以base与L+1位置的数交换，不影响区域的大小，但便于观察数据
    # 这样的话， 0-L 上的数小于base; L+1 的数等于base; L+2 至 N-1 位置上的数 大于等于 base

    Swap(a, L+1, key)
    return (a, L+1, base)

• 解题思路_2: 双指针法
  上面的方案，设立了一个游标 L 从左往右移动，使得 L 左侧的值小于base。但是i要从左往右遍历一次，速度不够快。
  这里可以改进一下，再增加一个游标 R，让其从右往左移动，使得 R 右侧的数，大于等于base。
  当L和R撞在一起的时候，就可以结束了。

def Partition_2(a):

    N = len(a)
    # 这里仍然取最后一个元素为base
    # 但是 L 不是从-1开始，而是从0开始；这是因为下面不是与L+1位置的数做交换了
    # 而是 L 和 R 两个游标指向的数做交换！即 L 和 R 指向各自区域内的边界位置
    L, R, key = 0, N-1, N-1
    base = a[key]
    while L < R:
    # L 一旦等于R了，就说明两个游标都已经将区域确立好了，就该停止了
    # 所以下面的步骤也需要注意这个停止条件
        while a[L] < base and L<R:
            # L 从0开始，如果L指向的数满足条件，则L就往右移动            
            L+=1
            # 如果L指向了大于等于base的数，就先跳出左侧区域循环，等着下面和R位置交换
        while a[R] >= base and L<R:
            # R 从 N-1 开始，如果R指向的数满足条件，则R就往左移动
            R-=1
            # 如果R指向了小于base的数，就先跳出右侧区域循环，等着下面和L位置交换

        # 执行到这里，如果不是 L>=R这个条件触发，那么一定是这样的情况：
        # L 指向的数大于等于base，R指向的数小于base
        # 则正好将它俩交换一下位置，然后进行下一次循环    
        if L< R: Swap(a, R, L)
        
    # 循环结束时 L==R，此时该位置的数必然 >= a[key]，直接将其交换
    # 这里之所以有这个结论，其实跟上面的一些设置有关系
    # 首先是选取的key是数组最右侧的数，其次是因为循环里先移动L的位置
    # 如果我们选择0作为key，那么就应该先移动右边的数，然后循环结束时，该位置的数一定<=a[0]
    # 这段解析可以细品一下，或者自己多找几个数组试一下  
    Swap(a, R, key)
    return(a, R, base)

3.2.2 经典快速排序问题

在了解了上面的分区域（partition）操作之后，就已经可以将其应用到快速排序中了。
快速排序其实也是一种分而治之思想在排序算法上的典型应用，而且使用了递归的方法。
不断的将数组分为更小的两块区域，使其在最小的区域上能有序，进而在全局都有序。

def QuickSort_1(a, L, R):
    '''经典快速排序'''
    if(L>=R):
        return a
    # partition stage            
    pl, pr, key = L, R, L
    # 这里选择 partition_2的思路来做分块partition
    # 这里选择每一次的0作为key，以及先移动右边的数，
    # 然后循环结束时，该位置的数一定 <=a[0]
    # 然后与 pl位置的进行交换

    while pl < pr:
        while a[pr] > a[key] and pl < pr:
            pr-=1
        while a[pl] <= a[key] and pl < pr:
            pl+=1
        if pl< pr: Swap(a,pl,pr)
    Swap(a,pl,key)
    # recursion stage
    QuickSort_1(a, L, pl-1)
    QuickSort_1(a, pl+1, R)
    return a

3.2.3 荷兰国旗问题

之前的Partition操作只要求分为两块区域，一部分小于等于，另一部分大于（或者一部分小于，另一部分大于等于）。
会发现，等于基准base的数，并不一定处于中间位置，尤其当有很多个数等于base的时候。
那么如果现在分为三块区域，即【小于，等于，大于】，就能加速排序过程。
举个例子，比如三个区域各有 N/3个数，那么下一轮迭代，就不用考虑等于区域的数了，就减少了计算量。
所以三块区域的 partition 问题，被称为【荷兰国旗问题】。
（可是荷兰国旗明明是横着的三块区域，我也不知道为什么当初人们起这个名字，我觉得更像法国国旗……）

def Partition_3(a):
    '''荷兰国旗问题，分三块'''
    N = len(a)
    # 这里还是选择两个游标，但注意，这里L又是从-1开始了，因为下面i是在和L+1的位置交换
    # R 从 N-1开始，但因为我们的key是选的N-1，所以R也相当于是从待分块的区域外开始
    # 也就是说， L 和 R 一开始都是没有指向待比较元素的
    L, R, key = -1, N-1, N-1
    base = a[key]

    # 这里其实就是i从初始游标L右侧开始，即 待比较区域 的第1个元素开始遍历
    # 如果只是对整个数组应用一次该函数，其实写 i=0 更好理解
    # 但是在遇到递归操作时，i不可能永远是从0开始，而写L+1能够适应这种变化
    i = L+1 
    while i <R:
        # 我们的目标是R及其右侧的区域是【大于区域】，所以若i==R，说明该停止了
        if a[i]<base:
        # 这里是最开始已经讲过的，左侧区域向右扩展，L和i都增加
            Swap(a, i, L+1)
            L+=1
            i+=1                       
        elif a[i] == base:
        # 这里的条件，L不扩展，但i继续向右侧遍历，相当于单独留了一个等于区域出来
            i+=1
                      
        else:
        # i 和 R-1位置上的数交换，就是和大于区域左侧的那个数交换，然后大于区域向左扩张（R-=1）
        # 其实和小于区域L的处理，是镜像的，很容易理解，一个往右扩张，一个往左扩张
            Swap(a, i , R-1)
            R -=1
            # i+=1 一定要注意！ 大于区域扩展之后，i不应该增加！！！
            # 因为这个数字是从原来R-1位置换过去的，我们其实还没有进行与base比较这个操作
            # 就是说这个数没有得到遍历，我们得又再看一下现在i位置的值和base的关系
    # 循环结束时， i==R
    # 然后 [L+1, R-1] 区间应当是等于 base的区域 
    # 这时候需要把一开始选择的key位置上的 base数放入该区域中
    # 也就是需要进行一次交换
    # 下方为何与 R 交换呢？因为这个base的位置key是在右侧，
    # 所以R位置上，的数本来就大于 base，把它交换到 key位置上，仍然处于右侧【大于区域】
    # 如果我们一开始的 key 选择的是左侧的数，比如0位置上的数
    # 这里就应该 Swap(a,L,key), L上的数本来就小于base，放到0位置上去也不会影响partition
    Swap(a, R , key) 
    # 此时：R 位置为base值，[R+1, N-1] 上的数大于 base; [L+1,R]上的数等于base; [0, L]上的值小于base
    # 如此一来，就分为了三个部分，且端点位置我们也能知道
    return (a, L, R, base)

3.2.4 利用荷兰国旗问题改进快速排序

快速排序的架构其实很简单，就是先Partition，然后递归左右两侧区域，
这里我们只需要把 Partition 的方法换成 3区域 的方法即可：

def QuickSort_2(a, L, R):
    '''利用荷兰国旗问题进行小加速'''
    if(L>=R):
        return a
    # partition stage    
    pl, pr, key = L-1, R, R
    # print(pl, pr, key)
    i = pl+1 # 注意，这里如果写i=0的话会导致右半部分出错！
    while i < pr:
        if a[i] < a[key]:
            Swap(a, i, pl+1)
            pl+=1
            i+=1
        elif a[i] == a[key]:
            i+=1
        else:
            Swap(a, i, pr-1)
            pr-=1
    # 循环结束时， i==pr
    
    Swap(a, pr, key)
    # recursion stage
    # 观察下面的输入游标发现：
    # 比起改进之前，中间的 [pl+1,pr] 这一部分若干个元素就可以不用计算了，达成加速
    QuickSort_2(a, L, pl)
    QuickSort_2(a, pr+1, R)

    return a

3.2.5 快速排序再改进

  前面的所有 Partition 方法，都是固定了一个位置的数，作为base来进行比较，大多数时候我们习惯直接用最右侧的数。

  但是这样就有一个问题，那就是当数据处于某一种情况的时候，每一次的取右侧那个数作为基准，可能都会导致有较多的swap操作。

  输入数据是我们不可控的，为了使得算法稳定，我们可以使得每一次的key，都是随机产生的，这样从统计学角度讲，会是比较稳定快速排序。

import random
def QuickSort_3(a, L ,R):
    '''对每次取的key做随机处理，可以再次改进'''
    if(L>=R):
        return a
    # partition stage    
    pl, pr = L-1, R
    key = random.randint(L,R) # 在 L~R范围上随机取一个位置
    Swap(a, key, R) # 但是还是将该数放到R位置上，这样就能复用之前的code了
    key = R # 再更新一下key
    # 这样虽然用的还是R，但是这里的R位置上的数，其实是随机从待排区域中抽取的
    i = pl+1 # 注意，这里如果写i=0的话会导致右半部分出错！
    while i < pr:
        if a[i] < a[key]:
            Swap(a, i, pl+1)
            pl+=1
            i+=1
        elif a[i] == a[key]:
            i+=1
        else:
            Swap(a, i, pr-1)
            pr-=1
    # 循环结束时， i==pr
    
    Swap(a, pr, key)
    # recursion stage
    QuickSort_2(a, L, pl)
    QuickSort_2(a, pr+1, R)

    return a