<!-- ここまでコピペ -->
そんな中，O(n)で動作するようなやばいソートもあります．例えば，計数ソート，基数ソート，バケットソートなど…．
■計数ソート(counting sort)
このソートでは，配列aがn個の要素a0, a1, …an-1,を持っていた時，以下を仮定します．
0≦ai<k
で，次のように処理を進めます．
1.配列aにおいて，iに等しい要素の個数ciを計算
2.1.の結果を用いて，ciがi以下の要素の個数を含むように計算
3.配列aの各要素aiがどこに位置するかをcaiで調べ，出力配列bに順次代入．
k=O(n)の時，このソートの計算量はO(n)です．
□コード
// 計数ソート
void countingSort(int[] a, int k){
int n=a.length;
int[] b=new int[n];
int[] c=new int[k];
for(int i=0; i<n; i++)
c[a[i]]++;
// c[i]はiに等しい要素の個数を含んでいる
c[0]--;
for(int i=1; i<k; i++)
c[i]+=c[i-1];
// c[i]はi以下の要素の個数-1を含んでいる
for(int i=n-1; i>=0; i--)
b[c[a[i]]--]=a[i];
System.arraycopy(b, 0, a, 0, n);
}
■基数ソート(radix sort)
基数ソートは，i桁目に関するソートを最下位桁から最上位桁まで繰り返します．
ソートは安定ソートなら何でもいいのですが，各桁の値のとる範囲が小さければ計数ソートを使うのが妥当です．
要素数がn，各桁の値の範囲が0からk-1(k種類)，桁数がdであるとします．各桁の計数ソートの実行時間は，O(n+k)となります．計数ソートはd回行われるので，基数ソートの実行時間はO(dn+kd)となります．dが定数，k=O(n)ならば，結局O(n)になるので，線形時間で動作するという事になります．
□適用例
ソートする配列
| 329 | 457 | 657 | 839 | 436 | 720 | 355 |
1桁目(1の位)に注目してソート
| 720 | 355 | 436 | 457 | 657 | 329 | 839 |
2桁目(10の位)に注目してソート．安定ソートを用いているので，下2桁はソートされています．
| 720 | 329 | 436 | 839 | 355 | 457 | 657 |
3桁目(100の位)に注目してソート．これで完全にソートされました．
| 329 | 355 | 436 | 457 | 657 | 720 | 839 |
□コード
各桁の値は，10進数ではなく2進数で計算しています．2進数では，各桁の値をシフト演算で求める事が出来る，という利点があります．
// 基数ソート
void radixSort(int[] a){
for(int i=0; i<32; i++)
// 安定ソートを用いてi桁目に関する配列をソートする
countingSort(a, i);
}
void countingSort(int[] a, int d){
int n=a.length;
int[] b=new int[n];
int[] c=new int[2];
for(int i=0; i<n; i++)
c[(a[i]>>d)&1]++;
c[0]--;
c[1]+=c[0];
for(int i=n-1; i>=0; i--)
b[c[(a[i]>>d)&1]--]=a[i];
System.arraycopy(b, 0, a, 0, n);
}
■バケットソート(bucket sort)
バケットソートでは，配列の各要素が区間[0, 1)に一様分布する実数だと仮定します．
配列aの要素数をnとします．
このソートでは，区間[0, 1)をn等分し，n個の要素を各バケットに分配します．
例えばn=10なら，
[0,0.1)，[0.1,0.2)，[0.2,0.3)，[0.3,0.4)，[0.4,0.5)，[0.5,0.6)，[0.6,0.7)，[0.7,0.8)，[0.8,0.9)，[0.9,1)．
その後，各バケットをソートし，順に繋げていくだけです．
この時のソートアルゴリズムは挿入ソートを用います．
挿入ソートの計算量はO(n2)(n個の要素に対して)ですが，色々あってほぼΘ(1)となります．さらに，バケット数がnですので，結果的にO(n)になるのですよ．
□コード
// バケットソート
void bucketSort(double[] a){
int n=a.length;
LinkedList<Double>[] list=new LinkedList[n];
for(int i=0; i<n; i++)
list[i]=new LinkedList<Double>();
for(int i=0; i<n; i++)
list[(int)(n*a[i])].add(a[i]);
for(int i=0, k=0; i<n; i++){
Double[] b=list[i].toArray(new Double[0]);
// リストlist[i]を挿入ソートでソートする
insertionSort(b);
for(double d : b)
a[k++]=d;
}
}
// 挿入ソート
void insertionSort(Double[] a){
int n=a.length;
for(int j=1; j<n; j++){
double key=a[j];
int i=j-1;
while(i>=0&&a[i]>key){
a[i+1]=a[i];
i--;
}
a[i+1]=key;
}
}
元ネタは，アルゴリズムイントロダクション第1巻より第9章 線形時間のソーティングでした．
