2

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

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)
4

2 回答 2

1

您的代码中的一些错误

  1. sort() 需要 4 个参数，因此 sort(array, part[0], part[1]) 失败。顺便说一句，深度不是必需的。
  2. if array[right] < array[left]:和sort(a, 0, len(a), 1)。当它是数组的长度时，Right 超出了数组的索引范围。
  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() 在开始时对数组进行分区，不要在同一递归中进行两次分区。只需调用排序（数组，...）。
  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) )
于 2012-05-21T05:09:36.440 回答
0

piv 似乎总是返回相同的值，是吗？也许 for 循环应该在 array[left:right] 上而不是在整个数组上？

于 2012-05-21T04:43:22.240 回答