鸽巢排序、桶排序

鸽巢排序：

用数组c表示鸽巢，索引位置表示值，索引位置的值表示出现次数，然后遍历数组c，输出数组值次数组索引。

package pac1;

public class Demo {

	/**
	 * @param args
	 * 鸽巢排序
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] arr={1,2,2,4,4,3,3,3,5};
		int max=5;   //待排数组中的最大数
		pigeonSort(arr, max);
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]+" ");
		}
	}

	public static void pigeonSort(int[] array, int max) {  
	    int[] c = new int[max+1];//max是array数组中的最大值
	    for(int i=0; i<array.length; i++)   
	        c[array[i]]++;  
	    //c数组只是统计元素出现次数
	    int k = 0;
	    for(int i=0; i<max; i++)   
	        for(int j=1; j<=c[i]; j++)  
	            array[k++] = i;  
	}
}
           

桶排序：

应用：对于给定数据区间的海量数据的排序很适合用桶排序。

将给定区间划分成相同大小的子区间，称为桶，按照子区间的大小，将待排序数组的元素划分到对应的桶中，分别在每个桶中进行排序，最后按桶的顺序将元素一一遍历。

例如要对大小为[1..1000]范围内的n个整数A[1..n]排序，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储(10..20]的整数，……集合B[i]存储((i-1)*10, i*10]的整数，i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。下图表示出了桶排序作用于有10个数的输入数组上的操作过程。

package pac1;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

public class Demo1{

	/**
	 * @param args
	 * 桶排序
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		double [] arr={0.78,0.23,0.55,0.12,0.35,0.17,0.26,0.98};
		bucketSort(arr);
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]+ " ");
		}
	}
	
	public static void bucketSort(double [] arr){
		int len=10; //假设这里要划分为10个桶
		ArrayList [] list =new ArrayList[10]; //每个桶由一个List表示
		//划分桶并添加元素
		for(int i=0;i<arr.length;i++){
			int temp=(int) Math.floor(10*arr[i]);
			if(list[temp]==null) {
				list[temp]=new ArrayList();
			}
			list[temp].add(arr[i]);		
		}
		
		//对每个List进行排序
		for(int i=0;i<len;i++){
			if(list[i]!=null) Collections.sort(list[i]);
		}
		
		//输出已排序的数组，类似鸽巢排序
		int k=0;
		for(int i=0;i<len;i++){
			if(list[i]!=null){
				Iterator it=list[i].iterator();
				while(it.hasNext()){
					Double d=(Double) it.next();
					arr[k++]=d;
				}
			}
		}
	}

}