集計ソートpython実装:再帰と非再帰
1409 ワード
再帰
原理は比較的簡単で,秩序配列の結合である.
非再帰バージョン
非再帰バージョンには追加のスペースは必要ありません.元の配列に直接カットマージ
原理は比較的簡単で,秩序配列の結合である.
def merge(a, b):
c = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] < b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
while i < len(a):
c.append(a[i])
i += 1
while j < len(b):
c.append(b[j])
j += 1
return c
def merge_sort(lists):
if len(lists) <= 1:
return lists
middle = len(lists) // 2
left = merge_sort(lists[:middle])
right = merge_sort(lists[middle:])
return merge(left, right)
非再帰バージョン
非再帰バージョンには追加のスペースは必要ありません.元の配列に直接カットマージ
def merge(seq, low, mid, high):
left = seq[low: mid]
right = seq[mid: high]
k = 0
j = 0
result = []
while k < len(left) and j < len(right):
if left[k] <= right[j]:
result.append(left[k])
k += 1
else:
result.append(right[j])
j += 1
result += left[k:]
result += right[j:]
seq[low: high] = result
def merge_sort(seq):
i = 1 # i
while i < len(seq):
low = 0
while low < len(seq):
mid = low + i #mid
high = min(low+2*i,len(seq))
if mid < high:
merge(seq, low, mid, high)
low += 2*i
i *= 2