JAvaアルゴリズムの基数ソート


package com.hym.test.algorithms;

public class RadixSort {
	private int[] arrayTest = { 5, 26, 1, 783, 23, 2, 62, 394, 9, 46 };

	public void radixSort(int[] number, int d) {
		int k = 0;
		int n = 1;
		int m = 1;//  
		int[][] temp = new int[number.length][number.length];
		int[] order = new int[number.length];
		while (m <= d) {
			for (int i = 0; i < number.length; i++) {
				int lsd = ((number[i] / n) % 10);
				temp[lsd][order[lsd]] = number[i];
				order[lsd]++;
			}
			for (int i = 0; i < d; i++) {
				if (order[i] != 0)
					for (int j = 0; j < order[i]; j++) {
						number[k] = temp[i][j];
						k++;
					}
				order[i] = 0;
			}
			n *= 10;
			k = 0;
			m++;
		}
	}

	public static void main(String[] args) {
		RadixSort sort = new RadixSort();
		sort.radixSort(sort.arrayTest, 10);

		for (int i = 0; i < sort.arrayTest.length; i++) {
			System.out.print(sort.arrayTest[i] + " ");
		}
	}
}

(radix sort)は「分配式ソート」(distribution sort)に属し、基数ソート法は「バケツ法」(bucket sort)またはbin sortとも呼ばれ、その名の通り、キー値の一部の情報を通して、ソートする要素をいくつかの「バケツ」に割り当て、ソートの役割を果たすために、基数ソート法は安定性のソートに属し、その時間複雑度はO(nlog(r)m)であり、rは取った基数であり、mはスタック数であり、場合によっては、基数ソート法の効率は他の比較ソート法よりも高い.
http://baike.baidu.com/view/1170573.htm