バケットソートのアルゴリズム

バケットソート。原理：ある区間のデータを1つのバケツに入れ、別の区間のデータを別のバケツに入れ、それぞれのバケツにデータを入れた後、データをソートしてコア処理を完了します。区間のサイズは自分で設定します。バケットの数は /+1 です。

印象が深まるような写真を。

public class BucketSort{
	public static int[] bucketSort(int[] arr) {
		if(arr==null
arr.length<2) return arr;
		int n = arr.length;
		int min = arr[0];
		int max = arr[0];
		for(int i=1;i<n;i++) { //最大値と最小値を見つける
if(max<arr[i]) max = arr[i];
			if(min>arr[i]) min = arr[i];
		}
		int d = max - min; //dは全区間の大きさを表す。
		int bucketNum = d/5+1; //バケット数 インターバルサイズは5に設定されている。
		ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);//バケツの配列を作る
for(int i = 0;i<bucketNum ; i++) {//バケットの初期化
			bucketList.add(new LinkedList());
		}
		int index;
		for(int i =0;i< n ;i++) {
		 //indexデータがあるバケツの場所を示す
			index = (arr[i]-min)/5; 
			//データを対応するバケツに入れる
			bucketList.get(index).add(arr[i]);
		}
		//各バケツのデータをソートする
for(int i=0;i<bucketNum;i++) {
			Collections.sort(bucketList.get(i));
		}
		index = 0;
		//各バケツからランク付けされたデータをarr配列に入れる
for(LinkedList<Integer> list:bucketList) {
			for(Integer element:list) {
				arr[index++] = element;
			}
		}
		return arr;
	}
	//テストケース
public static void main(String[] args) {
		int [] a = {4,6,5,2,9,1,8};
		BucketSort r1 = new BucketSort();
		a = r1.bucketSort(a);
		for(int j=0;j<a.length;j++) {
			System.out.print(a[j]+" ");
		}
	}
}