拨开荷叶行,寻梦已然成。仙女莲花里,翩翩白鹭情。
IMG-LOGO
主页 文章列表 使用Lambda的递回快速排序

使用Lambda的递回快速排序

白鹭 - 2022-03-14 1952 0 0

我正在尝试使用两种方法(交换、磁区)实作递回快速排序算法,同时在 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]

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

标签:

0 评论

发表评论

您的电子邮件地址不会被公开。 必填的字段已做标记 *