我在插入排序方面遇到了麻煩，我覺得我可能錯過了排序的重點并誤解了基本原理。我們得到了一個插入排序，它編輯了輸入它的數(shù)組。我們的任務(wù)是修改我們獲得的代碼，然后創(chuàng)建一個不會編輯原始數(shù)組的建設(shè)性插入排序這是我到目前為止的代碼def append(A, x): return A + [x] def insertionSort(A): B = [] B = append(B, A[0]) for i in range(1, len(A)): B = insert(B, A[i], i, A) return str(B)def insert(B, k, hi, A): print(B, k, hi) for x in range(hi-1, -1, -1): if B[x] <= k: B = append(B, k) return B B = append(B, A[x]) B[0] = k return Bprint(insertionSort([2,4,6,8,10,1,3,5,7,9]))然而，在列表中的第三個或第四個元素之后，它開始以相反的順序?qū)⑺许椖刻砑拥搅斜淼哪┪瞇2] 4 1[2, 4] 6 2[2, 4, 6] 8 3[2, 4, 6, 8] 10 4[2, 4, 6, 8, 10] 1 5[1, 4, 6, 8, 10, 10, 8, 6, 4, 2] 3 6[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3] 5 7[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3, 3, 1, 10, 8, 6, 5] 7 8[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3, 3, 1, 10, 8, 6, 5, 7] 9 9[1, 4, 6, 8, 10, 10, 8, 6, 4, 2, 1, 10, 8, 6, 4, 3, 3, 1, 10, 8, 6, 5, 7, 9]我無法理解為什么這是錯誤的。非常感謝任何可以提供幫助的人。
2 回答
一只甜甜圈
TA貢獻(xiàn)1836條經(jīng)驗 獲得超5個贊
反向問題出現(xiàn)在插入函數(shù)的 foror 循環(huán)中，當(dāng)您的循環(huán)達(dá)到這些值時，它會啟動反向模式
def insert(B, k, hi, A):
# when hi=5
for x in range(hi-1, -1, -1):
# x = 4
# here B[4] is 10 and k=1 so B[4] <= 1 is False
# you program does not execute the inside of if
# instead it jumps to B = append(B, A[x]) where A[4] == 10
# and the this loop goes in reverse mode from 4 to 0
# when x = 3
# B[x] = 8 so 8 is not less or equal of k where k = 1
# so it jumps again to B = append(B, A[x]) where A[x] = A[3] = 8
# so it append 8
# and so on
# when this loop is finished your list will look like [1,4,6,8,10,10,8,6,4,2]
# the 1 gets added when the loop is finished at B[0] = k
# and then rest of the outputs are result of the loop inside the insertionSort func
if B[x] <= k:
B = append(B, k)
return B
B = append(B, A[x])
B[0] = k
return B
這是一個解決方案：
def insertionSort(A):
copy_sort = A.copy()
for i in range(1, len(copy_sort)):
item = copy_sort[i]
j = i - 1
while j >= 0 and copy_sort[j] > item:
copy_sort[j + 1] = copy_sort[j]
j -= 1
copy_sort[j + 1] = item
return copy_sort
your_array = [2,4,6,8,10,1,3,5,7,9]
sorted = insertionSort(your_array)
print(your_array)
print(sorted)
瀟湘沐
TA貢獻(xiàn)1816條經(jīng)驗 獲得超6個贊
您需要在紙上制定算法，然后將這些步驟轉(zhuǎn)換為 Python 代碼。您實施的內(nèi)容令人費解且不正確。
最重要的insert是，對于它需要的信息以及它應(yīng)該如何完成它的工作感到非常困惑。從您的代碼中我可以看出，您希望此例程將給定值k插入到 list 中的適當(dāng)位置B。出于某種原因，您還傳入了列表A和該列表中的值的位置，這兩者都不適用。
你的日常工作很奇怪。從末尾開始B（使用i而不是B自身），代碼檢查 B 的元素；每次在列表中找到一個小于新值的值時，它都會將新值附加到B. 無論進(jìn)行何種比較，它都會附加Ato的相應(yīng)元素B。您沒有將元素插入到正確的位置。
重寫這段代碼。從最少的必要信息開始：
def insert(arr, new_val): # insert new_val into the list arr
現(xiàn)在，您的函數(shù)需要執(zhí)行兩個步驟：
找到合適的位置
new_val使用插入該位置的值創(chuàng)建一個新列表。
你返回那個新列表。
你能從那里繼續(xù)嗎？
添加回答
舉報
0/150
提交
取消