十大ソートアルゴリズム——カウントソート

以下は個人学習ノートの整理です.
原理:バケツソートの思想は、バケツソートの特例にすぎない.
手順:

は、各データの出現回数を統計するためのリストを定義する.

上記リスト要素を左から右への順に加算する.

は、ソート後のシーケンスを格納するためのリストを定義する.

は元のシーケンスの最後の要素からスキャンを開始し、対応するカウントリストの値-1はソートリストの下付きであり、対応する値はソートリストの対応する値である.

実装コード(python):

import itertools

def counting_sort(alist):
    '    ，        ，            '
    if len(alist) <= 1:
        return alist
    #      ，             
    counts = [0] * (max(alist) + 1)
    for num in alist:
        counts[num] += 1
    
    #     
    counts = list(itertools.accumulate(counts))   
    
    #      ，          
    sorted_list = [0] * len(alist)
    #            ，          -1        ，             
    for i in reversed(alist):
        index = counts[i] - 1
        sorted_list[index] = i
        counts[i] -= 1
        
    alist[:] = sorted_list
    return alist

複雑度解析:-空間複雑度空間複雑度O(n)
-時間複雑度–最適時間複雑度:O(n)-最悪時間複雑度:O(nlogn)-平均時間複雑度:O(n)
元のソートアルゴリズムに属するかどうか:元のソートアルゴリズムではありません
安定性あんていせい:安定性あんていせい
適応範囲:外部ソートに適応する、すなわちデータ量が比較的大きいが、データ範囲が比較的小さいソート