算法-排序-桶排序

文章将会同步到个人微信公众号:Android部落格

1.1 描述

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。

  • 设置一个定量的数组当作空桶;
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来。

1.2 代码

private static int getIndex(int value,int min){
	return (value - min) / 10;
}

public static void bucketSort(){
	int minValue = numbers[0];
	int maxValue = numbers[0];
	for(int index = 0;index < size;index++){
		if(numbers[index] < minValue){
			minValue = numbers[index];
		}
		if(numbers[index1] > maxValue){
			maxValue = numbers[index1];
		}
	}
	int bucketSize = maxValue / 10 - minValue / 10 + 1;
	int bucketIndex = 0;
	List<List<Integer>> bucketList = new ArrayList<List<Integer>>();
	for(int x = 0; x < bucketSize;x++){
		bucketList.add(new ArrayList<Integer>());
	}
	for(int index2 = 0;index2 < size;index2++){
		int tempIndex = getIndex(numbers[index2],minValue);
		List<Integer> tempList  = bucketList.get(tempIndex);
		tempList.add(numbers[index2]);	
	}
	int originIndex = 0;
	for(int index3 = 0;index3 < bucketSize;index3++){
		List<Integer> tempList = bucketList.get(index3);
		if(tempList == null || tempList.size() == 0){
			continue;
		}
		int tempSize = tempList.size();
		for(int i = 0;i < tempSize - 1;i++){
			for(int j = 0;j < tempSize - i - 1;j++){
				if(tempList.get(j) > tempList.get(j + 1)){
					int tempValue = tempList.get(j);
					tempList.set(j,tempList.get(j + 1));
					tempList.set(j + 1,tempValue);
				}
			}
		}
		for(int index4 = 0;index4 < tempSize;index4++){
			numbers[originIndex++] = tempList.get(index4);
		}
	}
}

public static void main(String []args) {
	bucketSort();
	for(int value : numbers){
		System.out.println("count value is:" + value);
	}
}

1.3 总结

  • 先遍历计算出最大值和最小值;
  • 最大值的高位减去最小值的高位,就是桶的数量,比如最大值为999,最小值为100,那么桶的数量等于99 - 10 + 1 = 90个,也就是每100个数设置10个桶;
  • 将元素值减去最小值,除以10,等于元素所属桶的序号;
  • 每一个桶内部再次使用排序算法排序,达到总体有序。

示意图如下: