python之荷兰国旗排序

我正在尝试使用 Dutch national flag algorithm 编写一个类似快速排序的算法.我已经尽我所能来完成这项工作，但我真的很沮丧。你能看一下并帮我找到错误吗？

import random 
 
a = [] 
for i in range(100): 
    a.append(random.randint(1, 100)) 
 
print(a) 
def partion(array, left, right, lPiv, rPiv): 
        high = len(array) -1 
        p = left 
        i = left 
        while i < high: 
                if array[i] < lPiv and array[i] < rPiv: 
                        array[i],array[p]=array[p],array[i] 
                        p = p+1 
                        i = i+1 
                elif array[i] > lPiv and array[i] > rPiv: 
                        array[i],array[high]=array[high],array[i] 
                        high = high-1 
                else: 
                        i = i+1 
 
        return [p, high] 
 
def piv(array, left, right): 
    aMin = array[left] 
    aMax = array[left] 
 
    for i in array: 
      if i < aMin: 
          aMin = i 
      if i > aMax: 
          aMax = i 
    return [aMin + ((aMax - aMin) /3), aMin + ((aMax-aMin)/3)*2] 
 
 
def sort(array, left, right, depth): 
    apiv = piv(array, left, right) 
    part = partion(array, left, right, apiv[0], apiv[1]) 
    if right-left >= 3: 
        piv1 = piv(array, left, part[0]) 
        part1 = partion(array, left, part[0], piv1[0], piv1[1]) 
        sort(array, left, part1[0], depth+1) 
 
 
        piv2 = piv(array, part[0], part[1]) 
        part2 = partion(array, part[0], part[1], piv2[0], piv2[1]) 
        sort(array, part[0], part[1]) 
 
        piv3 = piv(array, part[1], right) 
        part3 = partion(array, part[1], right, piv3[0], piv3[1] ) 
        sort(array, part[1], right) 
 
    elif right-left < 3: 
        if array[right] < array[left]: 
            array[right],array[left] = array[left], array[right] 
        else: 
            return 
 
 
sort(a, 0, len(a), 1) 
print(a) 

请您参考如下方法:

代码中的一些错误

1. sort() 有 4 个参数，所以 sort(array, part[0], part[1]) 失败了。顺便说一句，深度不是必需的。
2. if array[right] < array[left]:和 sort(a, 0, len(a), 1) . 右为数组长度时超出数组下标范围。
3. piv 应该处理部分而不是整个数组
4. 如果分区中的数字都相同，aMin + ((aMax - aMin) /3)和 aMin + ((aMax-aMin)/3)*2是同一个索引
5. 因为分区只处理一个分区而不是整个数组，high = len(array) -1应该是 high = right -1
6. part1 = partion(array, left, part[0], piv1[0], piv1[1])是错的。 Sort() 在开始时对数组进行分区，不要在同一个递归中进行两次分区。只需调用 sort(array,...)。
7. 您的分区算法有误，我找不到简单的修复方法

这是我的实现。

import random 
from itertools import islice 
a = [] 
for i in range(100): 
    a.append(random.randint(1, 100)) 
 
def partition(array, left, right, lPiv, rPiv): 
        q = right -1 
        p = left 
        r = left 
        while p<=q: 
            if array[p]<=lPiv: 
                array[p], array[r] = array[r], array[p] 
                p = p+1 
                r = r+1 
            elif lPiv<array[p]<=rPiv: 
                p = p+1 
            else: 
                array[p], array[q] = array[q], array[p] 
                q=q-1 
 
        return (p, q+1) 
 
def piv(array, left, right): 
    aMin = min(islice(a,left,right)) 
    aMax = max(islice(a,left,right)) 
    return (aMin + ((aMax - aMin) /3.0), aMin + ((aMax-aMin)/3.0)*2) 
 
 
def sort(array, left, right): 
    if right-left >= 3: 
        piv_left, piv_right = piv(array, left, right) 
        if piv_left == piv_right: 
            return 
        pt_left, pt_right = partition(array, left, right, piv_left, piv_right) 
        sort(array, left, pt_left) 
        sort(array, pt_left, pt_right) 
        sort(array, pt_right, right) 
    elif right-left <3: 
        if left<right and array[right-1] < array[left]: 
            array[right-1],array[left] = array[left], array[right-1] 
 
 
sort(a, 0, len(a)) 
print a 
 
#test 
assert( a==sorted(a) )