JAvaアルゴリズムの基数ソート
1549 ワード
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