8大ソートアルゴリズムのPython実装_6__集計ソート

1378 ワード

個人技術ブログアドレス:http://songmingyao.com/
げんり
  • は、最小(すなわち、各リストに1つの要素しかない)
  • までリストを再帰的に分解する.
  • リストを最小に分解した後、2つのリストを再帰的にマージします.すなわち、2つのリストの一番前の要素を1つずつ比較し、小さい人は新しいリストに追加します.その後、リストの下のラベルは1つ後ろに移動し、1つのリストが空になるまで比較を続けます.その後、別のリストの残りの要素を新しいリスト
  • に追加します.
  • は、完全なソートが完了するまでマージされ続けます.
    ソースコード
    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)
    

    時間の複雑さ
  • 最適時間複雑度:O(nlogn)
  • 最悪時間複雑度:O(nlogn)
  • 安定性(複数の元素が等値の場合は元の順序を破壊するかどうか):安定