我正在尝试使用两种方法（交换、磁区）实作递回快速排序算法，同时在 lambda 表达式中使用递回运行主演算法。我得到一个无限递回错误，老实说我找不到语法错误。有人可以帮我吗？谢谢 ：）

def swap(array, a, b):
        array[a], array[b] = array[b], array[a]
def partition(array, high, low):
    pivot = array[high]
    i = low
    for x in range(low, high-1):
        if array[x] < pivot:
            i =1
            swap(array, array[x], array[high])
    return i
g = lambda array, low, high: g(array,low,partition(array,high,low)-1) g(array,partition(array,high,low) 1,high) if low < high else print("not sorted")

uj5u.com热心网友回复：

有几个问题partition：

• 呼叫swap是从您的串列中传递值，而不是索引。

• 即使先前的错误被纠正，它也会将枢轴值移动到low 1索引中，或者根本不会移动。

• 回传的 indexi应该是枢轴移动的位置。在正确的实作中，这意味着i值被移动到的最后一个索引，即 index 处的值high。这不是正在发生的事情，因为第一次交换已经移动了枢轴值。

• 交换应该是当前值和 at 的值i，因此直到索引 at 的所有值i都小于或等于枢轴值。

这是修正后的partition函式：

def partition(array, high, low):
    pivot = array[high]
    i = low - 1
    for x in range(low, high 1):
        if array[x] <= pivot:
            i =1
            swap(array, x, i)
    return i

这些是函式中的问题g：

• 它应该就地执行排序，因此 串列运算子不应出现在此处，因为这会创建一个新串列。此外，基本情况 (in else) 不回传任何内容，因此 运算子将失败并出现错误

• partition(array,high,low)被呼叫两次，这不仅是浪费，而且第二次呼叫在大多数情况下会回传不同的结果，因为枢轴可以不同。这意味着第二次呼叫g可能不适用于相邻磁区，但会留下（未排序的）间隙，或者在重叠磁区上作业。

这是对功能的更正g：

def g(array, low, high):
    if low < high:
        i = partition(array, high, low)
        g(array, low, i-1)
        g(array, i 1, high)

您还应该考虑使用比 更好的名称g，并更改high/low自变量的顺序partition： 颠倒顺序是混淆代码读者的好方法。

uj5u.com热心网友回复：

这是Hoare在 Python 中实作的快速排序算法-

def quicksort(A, lo, hi):
  if lo >= 0 and hi >= 0 and lo < hi:
    p = partition(A, lo, hi)
    quicksort(A, lo, p)
    quicksort(A, p   1, hi)

def partition(A, lo, hi):
  pivot = A[(hi   lo) // 2]
  i = lo
  j = hi
  while True:
    while A[i] < pivot:
      i  = 1
    while A[j] > pivot:
      j -= 1
    if i >= j:
      return j
    swap(A, i, j)

def swap(A, i, j):
  A[i], A[j] = A[j], A[i]

如果你愿意，你可以写gusing lambda，但我建议改为def使用普通函式 -

g = lambda a: quicksort(a, 0, len(a) - 1)

给定一个样本输入，x-

x = [5,0,9,7,4,2,8,3,1,6]
g(x)
print(x)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

如果您想计算使用的比较和交换的数量，请参阅此相关问答。