如何在 Python 中实现双轴快速排序

Question

所以我一直在尝试在 Python 2.7 中重现双轴快速排序算法；最基本的运行完美：

def quicksort_by_length(list, start, top):
    if top <= start:
        return
    p = start
    k = start+1
    h = k
    while k <= top:
        if list[k] < list[p]:
            list[k], list[h] = list[h], list[k]
            h += 1
        k += 1
    h -= 1
    list[p], list[h] = list[h], list[p]
    quicksort_by_length(list, start, h-1)
    quicksort_by_length(list, h+1, top)

接下来，我转向双枢轴，这是我尝试过的：

def dual_pivot_sort(list, start, top):
    if top <= start:
        return
    p = start
    q = top
    k = p+1
    h = k
    l = q-1
    if list[p] > list[q]:
        list[p], list[q] = list[q], list[p]
    while k < top:
        if list[k] < list[p]:
            list[h], list[k] = list[k], list[h]
            h += 1
        elif list[k] > list[q]:
            list[k], list[l] = list[l], list[k]
            l -= 1
        k += 1
    h -= 1
    l += 1
    list[p], list[h] = list[h], list[p]
    list[q], list[l] = list[l], list[q]
    dual_pivot_sort(list, start, h-1)
    dual_pivot_sort(list, h+1, l-1)
    dual_pivot_sort(list, l+1, top)

在尝试几个列表时，此代码可以对反向列表进行排序，但无法处理运行dom 或先升后降列表：尝试对 [1, 2, 3, 4, 5 , 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1] 给出 [1, 1, 2, 3, 4, 5, 5, 6, 3, 4, 7, 2 , 6, 7, 8, 8, 9]。我缺少什么简单的东西吗？

Answer 1

def dual_pivot_sort(list, start, top):
    if top <= start:
        return
    p = start
    q = top
    k = p+1
    h = k
    l = q-1
    if list[p] > list[q]:
        list[p], list[q] = list[q], list[p]
    while k <= l: 
    # the last non-check index is l,as l+1 to top - 1 is the part III,              
    #where all elements > list[top] 
        if list[k] < list[p]:
            list[h], list[k] = list[k], list[h]
            #h is the first element of part II
            h += 1 
            #increase h by 1, for pointing to the first element of part II
            k += 1 
            #increase k by 1, because we have checked list[k]
        elif list[k] > list[q]:
        #l is the last element of part IV
            list[k], list[l] = list[l], list[k]
            #don't increase k, as we have not check list[l] yet
            l -= 1 
            #after swap, we should compare list[k] with list[p] and list[q] again
        else: k += 1
        # no swap, then the current k-th value is in part II, thus we plus 1 to k
    h -= 1#now,h is the last element of part I
    l += 1 #now, l is the first element of part III
    list[p], list[h] = list[h], list[p]
    list[q], list[l] = list[l], list[q]
    dual_pivot_sort(list, start, h-1)
    dual_pivot_sort(list, h+1, l-1)
    dual_pivot_sort(list, l+1, top)

II/III部分的定义和双轴排序的解释可以参考What's the difference of dual pivot quick sort and quick sort?

如何在 Python 中实现双轴快速排序

how to implement dual-pivot quicksort in Python

python

sorting

algorithm

quicksort

python-2.7