我正在使用 Python 遞歸實現(xiàn)快速排序，而無需創(chuàng)建新變量來保存分區(qū)數(shù)組的左右部分。運行遞歸步驟時我得到了錯誤的值。這是我到目前為止所做的：def swap(a,i,j): tmp = a[i] a[i] = a[j] a[j] = tmp def pivot(a, lo, hi): mid = (lo + hi) // 2 # sort lo, mid, hi: if a[mid] < a[lo]: swap(a, lo, mid) if a[hi] < a[lo]: swap(a, lo, hi) if a[hi] < a[mid]: swap(a, mid, hi)def partition(a, lo, hi): # place the pivot out of the way, in position hi -1 mid = (lo + hi)//2 swap(a, mid, hi - 1) i = lo j = hi - 1 pivot = a[j] while True: while True: i += 1 if a[i] >= pivot: break while True: j -= 1 if a[j] <= pivot: break if i >= j: break swap(a, i, j) swap(a, i, hi - 1) return i假設(shè)上面的模板代碼是“正確的”。我必須使用上述樞軸和分區(qū)的實現(xiàn)來實現(xiàn)快速排序。這就是我所做的：def quicksort(a): _sort(a, 0, len(a)-1) def _sort(a, left, right): if(left < right): pivot(a, left, right) piv = partition(a, left, right) _sort(a, left, piv-1) _sort(a, piv+1, right)當我用列表調(diào)用快速排序時：x = [98, 33, 11, 5, 1, 10, 11, 12, 14, 33, 55, 66, 556, 88]quicksort(x)print(x)>>> [1, 5, 10, 11, 11, 12, 14, 33, 33, 55, 66, 88, 556, 98]您可以看到 98 放錯了位置。如果我這樣跑：x = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6, 55, 66, 888, 33, 556, 10]quicksort(x)print(x)>>> [2, 3, 5, 6, 7, 9, 10, 10, 11, 12, 14, 33, 55, 66, 556, 888]所以，對于上述情況來說，它是正確的。但在其他較小的情況下它會失敗：x = [98, 33, 11, 556, 88]quicksort(x)print(x)>>> [33, 11, 88, 556, 98]誰能幫我找到錯誤嗎？謝謝 ：-）
1 回答
慕的地10843
TA貢獻1785條經(jīng)驗 獲得超8個贊
我看到兩個錯誤，第一個錯誤在您的partition()函數(shù)中。
嘗試替換swap(a, i, hi - 1)為swap(a, i, hi)
第二個是在_sort(). 最后一次通話應該是_sort(a, piv, right)
正確的代碼是：
def partition(a, lo, hi):
# place the pivot out of the way, in position hi -1
mid = (lo + hi)//2
swap(a, mid, hi - 1)
i = lo
j = hi - 1
pivot = a[j]
while True:
while True:
i += 1
if a[i] >= pivot: break
while True:
j -= 1
if a[j] <= pivot: break
if i >= j: break
swap(a, i, j)
swap(a, i, hi)
return i
和
def _sort(a, left, right):
if(left < right):
pivot(a, left, right)
piv = partition(a, left, right)
_sort(a, left, piv-1)
_sort(a, piv, right)
測試：
x = [98, 33, 11, 556, 88]
quicksort(x)
print(x)
[11, 33, 88, 98, 556]
更多測試：
import random
for n in range(10):
x = [random.randint(1,999) for i in range(random.randint(4,10))]
quicksort(x)
print(x)
[104, 226, 721, 769]
[131, 453, 590, 730, 752, 834]
[132, 156, 191, 277, 541, 599, 666, 909, 919]
[114, 210, 280, 919, 968, 978]
[127, 212, 381, 458, 585, 594, 685, 809, 935]
[73, 90, 189, 591, 599, 686, 806, 829, 831, 906]
[89, 115, 208, 601, 774, 813, 842, 981]
[159, 177, 203, 231, 621, 759, 950]
[347, 348, 417, 476, 850, 902]
[8, 50, 51, 483, 499, 696, 842]
添加回答
舉報
0/150
提交
取消