O（n）の値の範囲で配列を並べ替える

Question

配列A[1, ..., n]があり、それはすべて1 <= l <= n、次にA[l] in {1,2,...,n^5}となることが知られています。

O（n）でこれをソートする方法はありますか？

Answer 1

Base-nシステムでA[i]の値を表すとします。次に、各数値は5桁のn進数になります。つまり、 "radix"がnのRadix Sortの5つのアプリケーションで配列全体をソートすることができます。 /は整数除算を表し

D _X =（K /（N ^X））％N

：数kの各 "数字" Xの

計算値は次のように。整数の

Answer 2

ソート・リストでベース-N基数ソート、 も、これは単純なリスト

def rsort(a,N): 

if a: 
    bins = [ [],[],[],[],[] ] 

    m = max(a) 
    r = 1 

    while m > r: 
     for e in a: 
      bins[(e/r)%N].append(e) 

     r = r * N 
     a = [] 
     for i in range(N): 
      a.extend(bins[i]) 
      bins[i] = [] 

return a