線形時間ソート

最近のいくつかの文章はすべてソートアルゴリズムについて、みんなと一緒に進歩することを望んで、一緒にソート問題の本質と構想を深く理解します.私はアルゴリズムの面でまだ菜鳥の段階にあるので、文章の読者向けは広範なアルゴリズムの入門者で、達人の門が高く手を上げてほしいと思っています.
本論文では,線形時間並べ替えアルゴリズムについて議論し,非線形時間アルゴリズムについては別のテーマで議論する.
開編:御剣術---カウントダウン
カウントソートは、一言で言えば、各要素の個数を統計して、その最終的な位置を推定します.明らかに、その最終的な位置はそれより小さい数の要素の個数の和に等しいです.したがって、それより小さい要素の個数とを積算すれば、その最終的な位置がわかります.
したがって、カウント・ソートは2つのステップに分けられ、統計--累計
【統計】:各数の出現回数を1つの配列の各項目に置く
【累積】:配列の各項目の値を前の項目の和に等しくする
明らかに、エレメント自体の値を配列の下付きにすることで、前のアイテムが後のアイテムよりも小さいことを保証できます.

def countingSort(arr):
    MAX = 0
    buf = [0]
    result = range(len(arr))
    for i in arr:
        if i > MAX:
            MAX = i
    buf = [0 for i in range(MAX+1)]
    for i in arr:
        buf[i] += 1
    for i in range(1,MAX+1):
        buf[i] = buf[i-1] + buf[i]
    for i in range(len(arr))[::-1]:
        result[buf[arr[i]]-1] = arr[i]
        buf[arr[i]] = buf[arr[i]]-1
    return result

進級:万剣诀---基数序列
御剣術の改良版に属して、どこが改良しますか?適用範囲が広くなりました.御剣術は単一のキーワードのみを並べ替えることができ、万剣秘訣は複数のキーワードを並べ替えることができる.
基数ソートは、一言で言えば、各キーワードを低から高まで順に基数ソートし、結果として秩序シーケンスが得られる.ここではカウントソートの安定性を用いた.