2

我已经尝试实现快速排序 2 天了（看起来我的编程技能已经生锈了）。我不知道我做错了什么。我正要放弃，所以我想我应该咨询讨论论坛。

这是我试图在 python 中实现的代码。但它没有给出预期的结果。任何人都可以请指出我做错了什么？

def QuickSort(A,p,r):

if p < r:
    pivotIndex = Partition(A,p,r)
    QuickSort(A,p,pivotIndex-1)
    QuickSort(A,pivotIndex+1,r)
    return A
def Partition(A,p,r):

m = A[p]
i = p+1
for j in range( p+1 , r ):
    if A[j] < m:
        A[j] , A[i] = A[i] , A[j]
        i+=1
A[p], A[i-1] = A[i-1] , A[p]
return i-1

测试输入的输出是：

>>>QuickSort([9,8,7,6,5,4,3,2,1],0,9)
[1, 3, 5, 6, 7, 4, 8, 2, 9]

如果有人帮助我实现这一点，我将非常感激。

问候

4

4 回答 4

2

切片不会返回原始列表的视图；它根据旧列表中的数据创建一个新列表。这意味着递归调用QuickSort不会更改原始列表。

于 2013-07-15T17:22:04.940 回答
1

您可以在一行代码中尝试此实现：

def QuickSort(list):
    return [] if list==[]  else QuickSort([x for x in list[1:] if x < list[0]]) + [list[0]] + QuickSort([x for x in list[1:] if x >= list[0]])

print QuickSort([9,8,7,6,5,4,3,2,1])
于 2013-07-15T17:25:47.023 回答
1

我已经找到答案了。看来我正在向 QuickSort 方法传递一个-less

def QuickSort(A,p,r):
    if r-p <= 1: return
    pivotIndex = Partition(A,p,r)
    QuickSort(A,p,pivotIndex)
    QuickSort(A,pivotIndex+1,r)
    return A
def Partition(A,p,r):

    m = A[p]
    i = p+1

    for j in range( p+1 , r ):
        if A[j] < m:
            A[j] , A[i] = A[i] , A[j]
        i= i + 1
    A[p], A[i-1] = A[i-1] , A[p]
    return i-1

这是正确的实现

于 2013-07-15T18:33:42.307 回答
0

似乎您想将枢轴保留在左侧并跳过它，但结果并不好，所以我只是将它移到数组的末尾并相应地减少了迭代索引，然后反转了后分区交换（考虑到枢轴运动）。

def Partition(A,p,r):

  m = A[p]
  A[p], A[r] = A[r], A[p]
  i = p
  for j in range( p, r ):
    if A[j] < m:
        A[j] , A[i] = A[i] , A[j]
        i+=1
  A[r], A[i] = A[i] , A[r]
  return i

我认为你可以用左侧的枢轴来做到这一点，但是我猜你必须改变循环方向，但我不确定。

编辑：对不起，我忘了添加调用是 QuickSort([9,8,7,6,5,4,3,2,1],0, 8 )，因为索引现在包含在内。

于 2013-07-15T18:33:36.990 回答