1035 插入與歸并
插入排序是迭代演算法，逐一獲得輸入資料，逐步產生有序的輸出序列，每步迭代中，演算法從輸入序列中取出一元素，將之插入有序序列中正確的位置，如此迭代直到全部元素有序，
歸并排序進行如下迭代操作：首先將原始序列看成 N 個只包含 1 個元素的有序子序列，然后每次迭代歸并兩個相鄰的有序子序列，直到最后只剩下 1 個有序的序列，
現給定原始序列和由某排序演算法產生的中間序列，請你判斷該演算法究竟是哪種排序演算法？
Input
- 10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
Output
- Insertion Sort
1 2 3 5 7 8 9 4 6 0
n = int(input().strip())
org_lst = list(map(int, input().strip().split()))
sort_lst = list(map(int, input().strip().split()))
tar = org_lst[:]
flag = None
for i in range(1, n):
if i > 1 and tar == sort_lst: # (i>1是測驗點2的坑）
flag = 1
while i-1>=0 and tar[i-1] > tar[i]:
tar[i-1], tar[i] = tar[i], tar[i-1]
i -= 1
if flag == 1:
print('Insertion Sort')
for i in range(n):
if i == n-1:
print(tar[i])
else:
print(tar[i],end=' ')
break
if flag != 1:
def norecursionmerge(arr, low, mid, high):
left = arr[low:mid]
right = arr[mid:high]
i, j = 0, 0
ret = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
ret.append(left[i])
i += 1
else:
ret.append(right[j])
j += 1
ret += left[i:]
ret += right[j:]
arr[low:high] = ret
i = 1
while i < n:
low = 0
if org_lst== sort_lst:
flag = 0
while low < n:
mid = low + i
high = min(n, low+2*i)
if mid < high:
norecursionmerge(org_lst, low, mid, high)
low += 2*i
if flag == 0:
print('Merge Sort')
for i in range(n):
if i == n-1:
print(org_lst[i])
else:
print(org_lst[i],end=' ')
break
i *= 2
由于用的非遞回看起來有點啰嗦，具體代碼排版也沒有深究，
測驗點2的坑輸入的是
- 3
- 1 3 2
- 1 3 2
按照插入排序1 3 2既可以是剛剛開始的時候也可以是第一步結束
如果剛剛開始那么下一步依然是1 3 2 如果是第一步結束那么下一步應該是1 2 3 但是顯然測驗將1 3 2 做為第一步結束后的，應該輸出1 2 3
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/230303.html
標籤：python