我正在嘗試在 Python 中實作 3 路磁區快速排序代碼。
我的代碼有 2 行：
- 第一個是要排序的整數個數
- 第二個是要排序的整數陣列
我的代碼適用于以下輸入：
- 8, 1 3 5 4 2 6 4 4
- 5, 2 3 9 2 2
但是，當使用以下輸入進行測驗時：10, 10 9 8 7 6 5 4 3 2 1
我的代碼沒有正確排序整數陣列？
我可以知道為什么我的代碼不適用于最后一種情況嗎？
這是我的代碼：
def partition3(a, l, r):
#write your code here
pivot = a[r]
i = l
j = l - 1
iterable_length = r
while i <= iterable_length:
if a[i] < pivot:
j = 1
a[i], a[j] = a[j], a[i]
elif a[i] > pivot:
a[i], a[iterable_length] = a[iterable_length], a[i]
iterable_length -= 1
i = 1
return j, iterable_length 1
def randomized_quick_sort(a, l, r):
if l >= r:
return
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
#use partition3
# m = partition2(a, l, r)
m1, m2 = partition3(a, l, r)
randomized_quick_sort(a, l, m1);
randomized_quick_sort(a, m2, r);
if __name__ == '__main__':
input = sys.stdin.read()
n, *a = list(map(int, input.split()))
randomized_quick_sort(a, 0, n - 1)
for x in a:
print(x, end=' ')
uj5u.com熱心網友回復：
歡迎來到 StackOverflow。問題似乎在這里：
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
您正在獲得一個隨機索引并k使用它來隨機交換兩個元素。洗掉這兩行應該只在某些情況下才能得到正確的輸出。a[l]a[k]
我假設您正在尋找創建一個隨機樞軸點，在這種情況下，您應該使用隨機索引作為partition3函式內部的樞軸。
編輯：問題不是a[i]在交換 inside 后處理/跳過新元素a[i] > pivot:。它應該是：
elif a[i] > pivot:
a[i], a[iterable_length] = a[iterable_length], a[i]
iterable_length -= 1
# don't forget to process new element at a[i]
i -= 1
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/462145.html