我已经为插入排序和合并排序编写了代码。现在我想实现我的插入排序并将排序合并为 Tim 排序。
我可以看到 Tim 排序的示例使用了 start、mid 和 end 输入,但应该可以在没有 no 的情况下做到这一点?
如果可能的话,我想保持我的合并和插入排序,因为输入输出非常适合我的其余代码。
from random import randint
minrun = 32
def insertion_sort(in_data):
s_data = list(in_data)
for i in range(1, len(s_data)):
key = s_data[i]
j = i - 1
while j >= 0 and key < s_data[j]:
s_data[j + 1] = s_data[j]
j -= 1
s_data[j + 1] = key
return s_data
def merge(a, b):
c = []
a_idx, b_idx = 0, 0
while a_idx < len(a) and b_idx < len(b):
if a[a_idx] < b[b_idx]:
c.append(a[a_idx])
a_idx += 1
else:
c.append(b[b_idx])
b_idx += 1
if a_idx == len(a):
c.extend(b[b_idx:])
else:
c.extend(a[a_idx:])
return c
def merge_sort(a):
if len(a) <= 1:
return a
left, right = merge_sort(a[:len(a) // 2]), merge_sort(a[len(a) // 2:])
return merge(left, right)
def tim_sort(in_data):
n = len(in_data)
for start in range(0, n, minrun):
end = min(start + minrun - 1, n - 1)
in_data = insertion_sort(in_data, start, end)
curr_size = minrun
while curr_size < n:
for start in range(0, n, curr_size * 2):
mid = min(n - 1, start + curr_size - 1)
end = min(n - 1, mid + curr_size)
in_data = merge_sort(in_data, start, mid, end)
curr_size *= 2
return in_data
def create_array(size=10, max=50):
from random import randint
return [randint(0, max) for _ in range(size)]
我找到了 Tim sort 的这个例子,但我很纠结如何让它在我的代码中工作。