我試圖在快速排序中計算交換和比較操作。我想我將計數器設定在正確的位置，但由于遞回，我從來沒有得到這些值的正確數量。為了在整個遞回程序中“存盤”這些值，我將它們作為引數（qui_swap 和 qui_comp.
例如：當我讓這個演算法對一個包含 500 個整數的串列進行排序時，它會回傳 120 次交換和 1 次比較。
下面是我的代碼：
qui = quicksort(numbers, 0, len(numbers)-1, 0, 0)
def partition(numbers, start_index, end_index, qui_swap):
# Select the middle value as the pivot.
midpoint = start_index (end_index - start_index) // 2
pivot = numbers[midpoint]
# "low" and "high" start at the ends of the list segment
# and move towards each other.
low = start_index
high = end_index
done = False
while not done:
# Increment low while numbers[low] < pivot
while numbers[low] < pivot:
low = low 1
# Decrement high while pivot < numbers[high]
while pivot < numbers[high]:
high = high - 1
# If low and high have crossed each other, the loop
# is done. If not, the elements are swapped, low is
# incremented and high is decremented.
if low >= high:
done = True
else:
temp = numbers[low]
numbers[low] = numbers[high]
numbers[high] = temp
low = 1
high -= 1
qui_swap = 1
# "high" is the last index in the left segment.
return (high, qui_swap)
def quicksort(numbers, start_index, end_index, qui_swap, qui_comp):
# Only attempt to sort the list segment if there are
# at least 2 elements
if end_index <= start_index:
return
# Partition the list segment
#count comparisons here
qui_comp = 1
high = partition(numbers, start_index, end_index,qui_swap)
qui_swap = high[1]
# Recursively sort the left segment
quicksort(numbers, start_index, int(high[0]), qui_swap, qui_comp 1)
# Recursively sort the right segment
quicksort(numbers, int(high[0]) 1, end_index, qui_swap, qui_comp 1)
return(qui_swap, qui_comp)
uj5u.com熱心網友回復：
您的快速排序回傳計數器的更新值。但是您不分配它們。
快速排序函式的最后 5 行應該是：
# Recursively sort the left segment
l_swap, l_comp = quicksort(numbers, start_index, int(high[0]), qui_swap, qui_comp 1)
# Recursively sort the right segment
r_swap, r_comp = quicksort(numbers, int(high[0]) 1, end_index, qui_swap, qui_comp 1)
qui_swap = l_swap r_swap
qui_comp = l_comp r_comp
return(qui_swap, qui_comp)
（并且您還需要將裸回傳更改為：
if end_index <= start_index:
return(qui_swap, qui_comp)
uj5u.com熱心網友回復：
鑒于Hoare 的快速排序演算法-
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
A[i], A[j] = A[j], A[i]
我將首先從partition功能開始，包括comp和swap計數器 -
def partition(A, lo, hi):
comp = 0 # comparison counter
swap = 0 # swap counter
pivot = A[(hi lo) // 2]
i = lo
j = hi
while True:
while A[i] < pivot:
comp = 1 # increase comparison count
i = 1
while A[j] > pivot:
comp = 1 # increase comparison count
j -= 1
if i >= j:
return (comp, swap, j) # return comp, swap, and j
swap = 1 # increase swap count
A[i], A[j] = A[j], A[i]
partition現在回傳一個 3 元組，(comp, swap, j)所以我們需要相應地調整quicksort-
def quicksort(A, lo, hi):
if lo >= 0 and hi >= 0 and lo < hi:
(comp, swap, p) = partition(A, lo, hi) # receive 3-tuple
quicksort(A, lo, p)
quicksort(A, p 1, hi)
為了讓呼叫者接收這些資訊，我們必須格式化quicksort的回傳值。我們可以從回傳開始(comp, swap)——
def quicksort(A, lo, hi):
if lo >= 0 and hi >= 0 and lo < hi:
(comp, swap, p) = partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p 1, hi)
return (comp, swap) # return comp, swap
但這僅包括第一遍的比較和交換計數器。現在我們知道quicksort回傳一個 2 元組，(comp, swap)我們也可以從遞回呼叫中獲取它們 -
def quicksort(A, lo, hi):
if lo >= 0 and hi >= 0 and lo < hi:
(comp, swap, p) = partition(A, lo, hi)
(lcomp, lswap) = quicksort(A, lo, p) # left comp, swap
(rcomp, rswap) = quicksort(A, p 1, hi) # right comp, swap
return (comp lcomp rcomp, swap lswap rswap) # sum comp, swap
目前quicksort在if分支下只有一個回傳值，除此之外它隱式回傳None。在這種情況下，我們需要提供空comp和swap計數器 -
def quicksort(A, lo, hi):
if lo >= 0 and hi >= 0 and lo < hi:
(comp, swap, p) = partition(A, lo, hi)
(lcomp, lswap) = quicksort(A, lo, p)
(rcomp, rswap) = quicksort(A, p 1, hi)
return (comp lcomp rcomp, swap lswap rswap)
return (0,0) # base case, return empty counters
我們完成了！我們的 newquicksort回傳一個值，因此請確保將其存盤到變數中，print否則 -
x = [5,0,9,7,4,2,8,3,1,6]
print(quicksort(x, 0, len(x)-1))
print(x)
結果 -
(31, 9) # 31 comparisons, 9 swaps
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # sorted result
現在x是排序的。如果我們重復quicksort，我們會得到不同的比較和交換計數器 -
print(quicksort_stat(x, 0, len(x)-1))
print(x)
(25, 0) # 25 comparisons, 0 swaps
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # sorted result
而對于小型陣列，我們可以更輕松地驗證結果——
y = [2,1,3]
print(quicksort_stat(y, 0, len(y)-1))
print(y)
(3, 1) # 3 comparisons, 1 swap
[1, 2, 3] # sorted result
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/405872.html
標籤：
上一篇：在遞回中使用回傳與不回傳？
下一篇：計算嵌套物件和陣列的鍵總數