十大並べ替えアルゴリズム——バケツ並べ替え

以下は個人学習ノートの整理です.
原理:並べ替えられるデータをいくつかの秩序あるバケツに分けて、各バケツのデータは単独で並べ替えて、バケツ内の並べ替えが終わった後、順番に順番に取り出して、秩序あるシーケンスを構成します.
手順:

は、所望のバケツの数を決定するためにシーケンス中の最大値と最小値を探し出す.

データを対応するバケツに入れる.

バケツ内のデータをソートし、速排などのアルゴリズムに従ってソートすることができる.

バケツ内のデータは、秩序正しく取り出され、完全な秩序配列に結合される.

実装コード(python):

from quick_sort import quick_sort    #        

def bucket_sort(alist, bucketsize):
    minValue = alist[0]
    maxValue = alist[1]
    
    for i in alist:
        if i < minValue:
            minValue = i
        elif i > maxValue:
            maxValue = i
    #           
    bucketcount = (maxValue - minValue +1) // bucketsize
    #    
    bucket_lists = list([] for _ in range(bucketcount))
    
    #         
    for i in alist:
        bucket_index = (i - minValue) // bucketsize
        bucket_lists[bucket_index].append(i)
     
    
    #        
    for j in bucket_lists:
        quick_sort(j, 0, len(j)-1)     #        ，        ，      ，         
    
    #           
    result = []
    for j in bucket_lists:
        if len(j) != 0:
            result.extend(j) 
    return result

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