我必須使用插入排序和使用遞回而不使用回圈對陣列進行排序。我試過，但它沒有排序任何東西。這是我的代碼：
def recursiveInsertionSort(array, i, j):
n = len(array)
if i < n:
temp = array[i]
j = i - 1
if j >= 0 and array[j] > temp:
array[j 1] = array[j]
recursiveInsertionSort(array, i, j - 1)
array[j 1] = temp
recursiveInsertionSort(array, i 1, j)
return array
arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(recursiveInsertionSort(arr, 1, 0))
輸出是[10, 8, 7, 50, 60, 3, 9, -1]與給定陣列相同。預期輸出是[-1, 3, 7, 8, 9, 10, 50, 60]誰能幫我找出問題所在？
uj5u.com熱心網友回復：
老實說，您的代碼中有太多錯誤讓我無法列出，但這有效：
def recursiveInsertionSort(array, i, j):
n = len(array)
if i < n and j >= 0:
if array[j] > array[j 1]:
temp = array[j 1]
array[j 1] = array[j]
array[j] = temp
recursiveInsertionSort(array, i, j - 1)
if j == 0:
recursiveInsertionSort(array, i 1, i)
return array
arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(recursiveInsertionSort(arr, 1, 0))
輸出：
[-1, 3, 7, 8, 9, 10, 50, 60]
uj5u.com熱心網友回復：
遞回是一種函式式遺產，因此以函式式風格使用它會產生最好的結果。這意味著避免諸如突變、變數重新分配和其他副作用之類的事情。
我們可以insertion_sort(t)使用歸納推理來寫作。從輸入源src = t和一個空的目標陣列開始dst = []-
- 如果
src為空，則無需排序。回傳dst陣列 - (inductive)
src至少有一個元素。insert第一個元素src[0]進入dst子問題并在子問題上重復出現src[1:]
def insertion_sort(t):
def run(src, dst):
if not src:
return dst # 1
else:
return run(src[1:], insert(dst, src[0])) # 2
return run(t, [])
insert(t, x) 可以使用相同的技術撰寫 -
- 如果輸入
t為空，則唯一可能的輸出是[x] - (inductive)
t至少有一個元素。如果第一個元素t[0]小于要插入的元素x，則附加t[0]到遞回子問題的結果insert(t[1:], x) - （歸納）
t第一個元素大于或等于x。前置x到t
def insert(t, x):
if not t:
return [x] # 1
elif t[0] < x:
return [t[0]] insert(t[1:], x) # 2
else:
return [x] t # 3
最后列印結果
arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(insertion_sort(arr))
[-1, 3, 7, 8, 9, 10, 50, 60]
形象化
寫出評估步驟有助于我們可視化遞回計算的增長方式。首先我們來看兩者中較簡單的一個，insert(t,x)
insert([3, 7, 8, 10, 50, 60], 9)
== [3] insert([7, 8, 10, 50, 60], 9)
== [3] [7] insert([8, 10, 50, 60], 9)
== [3] [7] [8] insert([10, 50, 60], 9)
== [3] [7] [8] [9] [10, 50, 60]
== [3, 7] [8] [9] [10, 50, 60]
== [3, 7, 8] [9] [10, 50, 60]
== [3, 7, 8, 9] [10, 50, 60]
== [3, 7, 8, 9, 10, 50, 60]
現在讓我們想象一下insertion_sort(t)——
insertion_sort([10, 8, 7, 50, 60, 3, 9, -1])
== run([10, 8, 7, 50, 60, 3, 9, -1], [])
== run([8, 7, 50, 60, 3, 9, -1], [10])
== run([7, 50, 60, 3, 9, -1], [8, 10])
== run([50, 60, 3, 9, -1], [7, 8, 10])
== run([60, 3, 9, -1], [7, 8, 10, 50])
== run([3, 9, -1], [7, 8, 10, 50, 60])
== run([9, -1], [3, 7, 8, 10, 50, 60])
== run([-1], [3, 7, 8, 9, 10, 50, 60])
== run([], [-1, 3, 7, 8, 9, 10, 50, 60])
== [-1, 3, 7, 8, 9, 10, 50, 60]
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/380104.html
上一篇：字典葉生成器
下一篇：為什么函式不執行特定行