8大ソートアルゴリズムのPython実装_6__集計ソート
1378 ワード
個人技術ブログアドレス:http://songmingyao.com/
げんりは、最小(すなわち、各リストに1つの要素しかない) までリストを再帰的に分解する.リストを最小に分解した後、2つのリストを再帰的にマージします.すなわち、2つのリストの一番前の要素を1つずつ比較し、小さい人は新しいリストに追加します.その後、リストの下のラベルは1つ後ろに移動し、1つのリストが空になるまで比較を続けます.その後、別のリストの残りの要素を新しいリスト に追加します.は、完全なソートが完了するまでマージされ続けます.
ソースコード
時間の複雑さ 最適時間複雑度:O(nlogn) 最悪時間複雑度:O(nlogn) 安定性(複数の元素が等値の場合は元の順序を破壊するかどうか):安定
げんり
ソースコード
def merge_sort(l):
#
n = len(l)
if n <= 1:
return l
mid_posi = n//2
# print(1)
l_list = merge_sort(l[:mid_posi])
# print(2)
r_list = merge_sort(l[mid_posi:])
# print(3)
#
sorted_list = []
l_posi = 0
r_posi = 0
# print('l_list: %s' % l_list)
# print('r_list: %s' % r_list)
while l_posi < len(l_list) and r_posi < len(l_list):
if l_list[l_posi] <= r_list[r_posi]:
sorted_list.append(l_list[l_posi])
l_posi += 1
else:
sorted_list.append(r_list[r_posi])
r_posi += 1
#
sorted_list += l_list[l_posi:]
sorted_list += r_list[r_posi:]
# print('sorted_list: %s' % sorted_list)
return sorted_list
if __name__ == '__main__':
l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
print(l)
sorted_list = merge_sort(l)
print(sorted_list)
時間の複雑さ