双轴快速排序

双轴快排(DualPivotQuicksort),有两个轴元素pivot1,pivot2,且pivot ≤ pivot2,将序列分成三段:x < pivot1、pivot1 ≤ x ≤ pivot2、x > pivot2,然后分别对三段进行递归。

先简易实现它,然后按照java历次更改的初衷进行更改。简易实现唯一需要注意的是并非每次循环有效。

def dual_quick_sort(arr: [], start, end) -> None:
    if start >= end:
        return
    # 保证基准值左小右大
    if arr[start] > arr[end]:
        swap(arr, start, end)
    # 目前采用最简单的方式来选择基准值,开头和结尾
    pivot1, pivot2 = arr[start], arr[end]
    less, great = start, end
    # less 是飞行员阵营右边界,向右自增,直到碰上不符合飞行员条件的士兵
    while less + 1 <= end and arr[less] < pivot1:
        less += 1
    # great 是陆战队阵营左边界,向左减少,直到碰上不符合陆战队条件的士兵
    while great - 1 >= start and arr[great] > pivot2:
        great -= 1
    # K相当于募兵指导员,负责给两个阵营送合格的士兵
    k = less + 1
    # 只有K发现合格的士兵,相应的阵营才会扩大一个位置,把相应位置的士兵和K进行交换
    while k < great:
        if arr[k] < pivot1:
            less += 1
            swap(arr, less, k)
            k += 1
        elif pivot1 <= arr[k] <= pivot2:
            k += 1
        elif arr[k] > pivot2:
            great -= 1
            swap(arr, k, great)
    swap(arr, start, less)
    swap(arr, end, great)
    dual_quick_sort(arr, start, less - 1)
    dual_quick_sort(arr, less + 1, great - 1)
    dual_quick_sort(arr, great + 1, end)

def swap(arr: [], i, j):
    arr[i], arr[j] = arr[j], arr[i]

改良后的双轴排序原理图:

双轴快速排序

 

# -*- coding: utf-8 -*-
"""
-------------------------------------------------
   开发人员:Edwin
   开发日期:
   开发工具:PyCharm
   功能描述:
   
-------------------------------------------------
"""


def dual_quick_sort(arr:[], start, end) -> None:
    if start >= end:
        return
    # 保证基准值左小右大,相等不操作
    if arr[start] > arr[end]:
        swap(arr, start, end)
    # 目前采用最简单的方式来选择基准值,开头和结尾
    pivot1, pivot2 = arr[start], arr[end]
    less, great = start, end
    # less 是飞行员阵营右边界,向右自增,直到碰上不符合飞行员条件的士兵
    while less + 1 <= end and arr[less + 1] < pivot1:
        less += 1
    # great 是陆战队阵营左边界,向左减少,直到碰上不符合陆战队条件的士兵
    while great - 1 >= start and arr[great - 1] > pivot2:
        great -= 1
    # K相当于募兵指导员,负责给两个阵营送合格的士兵
    k = less + 1

    # java工业双轴排序引入复杂性,是因为保证每次循环有效。
    # java内部为了解决这个问题让两个阵营都可以就近自主招兵,尤其是右侧阵营,碰上不符合条件的就止步。
    # 但python没有自增运算符,所以保证阵营内都是符合条件的士兵,这一点跟java不同。
    # 陆战队扩充兵营时碰上符合飞行员条件的士兵直接送到飞行员阵营。
    # 但陆战队自主招兵的时机是募兵指导员发现了符合陆战队的士兵,反正都要扩充军营,顺便看看左侧还有没有符合条件的士兵。
    # 如果陆战队送过来飞行员,那么飞行员阵营也顺便看看右侧有没有符合条件的士兵。如果发现就带着募兵指导员一起招兵。
    # 飞行员阵营移动方向跟募兵指导员方向一致,所以飞行员阵营自主招兵可以省略。

    while k < great:
        if arr[k] < pivot1:
            less += 1
            swap(arr, less, k)
        elif arr[k] > pivot2:
            great -= 1
            if arr[great] < pivot1:
                less += 1
                arr[k], arr[less], arr[great] = arr[less], arr[great], arr[k]
                # -----del------如下代码可以删除,如果飞行员阵营和募兵指导员一前一后连续,同时三方交换完成后,之下都是单调非增函数
                # 数据,那么此行为才会执行,但大多数情况是无用的,如果优化可以删除。
                while less + 1 < great and arr[less + 1] < pivot1:
                    less += 1
                    k = less
                # -----del------------------
            elif pivot1 <= arr[great] <= pivot2:
                swap(arr, k, great)
            while great - 1 >= k and arr[great - 1] > pivot2:
                great -= 1
        k += 1
    swap(arr, start, less)
    swap(arr, end, great)
    dual_quick_sort(arr, start, less - 1)
    dual_quick_sort(arr, less + 1, great - 1)
    dual_quick_sort(arr, great + 1, end)


def swap(arr: [], i, j):
    arr[i], arr[j] = arr[j], arr[i]

def is_sorted(alist: []):
    prev = alist[0]
    for i in range(1, len(alist)):
        if prev > alist[i]:
            print('Sort ascending failed.')
            return False
        prev = alist[i]
    print('Sort ascending succeed.')
    return True

def test():
    import random
    n = 100000000
    alist = [random.randint(1, n) for i in range(n)]
    # alist = [12,11,]
    # print('Before: ', alist)
    dual_quick_sort(alist, 0, len(alist) - 1)
    print('After: ', alist)
    is_sorted(alist)
if __name__ == '__main__':
    test()

 

上一篇:DAY15—栈、队列、排序


下一篇:获取打印页号列表