我正在嘗試使用兩種方法（交換、磁區）實作遞回快速排序演算法，同時在 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索引中，或者根本不會移動。回傳的 index
i應該是樞軸移動的位置。在正確的實作中，這意味著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：
它應該就地執行排序，因此
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]
如果您想計算使用的比較和交換的數量，請參閱此相關問答。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409378.html
標籤：