实施3向快速排序

Question

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

这是一个quicksort函数(代表数组):

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

Answer 2

这是python中一个简单的快速实现.虽然它仍然是nlogn,但可以进行一系列性能优化.例如,可以在单次传递中进行分区为更小,相等,更大,而不是数组的3次传递.

def qsort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[0]
    less    = [x for x in arr if x < pivot]
    equal   = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return qsort(less) + equal + qsort(greater)

要使该分区在数组的一次传递中发生,请创建一个如下的辅助函数:

def partition(arr, pivot):
    less, equal, greater = [], [], []
    for val in arr:
        if val  < pivot: less.append(val)
        if val == pivot: equal.append(val)
        if val  > pivot: greater.append(val)
    return less, equal, greater

def qsort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[0]
    less, equal, greater = partition(arr, pivot)
    return qsort(less) + equal + qsort(greater)