python - 实现三向快速排序

Question

我是算法的新手，我很困惑我作为作业编写的代码中的错误在哪里。我正在尝试在 Python 3 中实现一种处理数组中相等值的快速排序算法。

这是一个快速排序函数(a 代表数组):

def randomized_quick_sort(a, l, r):
    if l >= r:
        return
    k = random.randint(l, r)
    a[l], a[k] = a[k], a[l]
    m1, m2 = partition3(a, l, r)
    randomized_quick_sort(a, l, m1 - 1);
    randomized_quick_sort(a, m2 + 1, r);

这是我的分区函数:

def partition3(a, l, r):
    x, j, t = a[l], l, r
    for i in range(l + 1, r + 1):
        if a[i] < x:
            j +=1
            a[i], a[j] = a[j], a[i]
        elif a[i] > x:
            a[i], a[t] = a[t], a[i]
            t -=1
        else:
            j +=1
    a[l], a[j] = a[j], a[l]
    return j, t

Answer 1

你应该纠正你的分区函数:

这是一个工作示例:

def partition3(a, l, r):
   x, j, t = a[l], l, r
   i = j

   while i <= t :
      if a[i] < x:
         a[j], a[i] = a[i], a[j]
         j += 1

      elif a[i] > x:
         a[t], a[i] = a[i], a[t]
         t -= 1
         i -= 1 # remain in the same i in this case
      i += 1   
   return j, t