（8）排序算法——分配式排序之桶排序

发表于   |   分类于   |   阅读次数

1、概述：

桶排序是将数组的N个元素分到M个桶里，每个桶里多于一个元素的话再排序，排序可以使用桶排序或者其他排序方法。桶排序不是比较排序，所以它的时间复杂度不受O(n log n)为下限的影响。

桶排序的算法要求，要排序的数据长度必须完全一样。也就是数据的位数相同，一位都是一样，三位都是三位数。

2、分析：

桶排序的时间复杂度包括两个部分：

  1. 循环计算每个元素的桶映射函数，这部分是O(N)。
  2. 利用排序算法对每个桶内的数据进行排序，这部分是∑O(Ni*logNi)，其中Ni为第i个桶中的元素个数。

第二部分决定了该排序的效率，因为比较排序的时间复杂度最低只能到O(N*logN)，因此我们应当尽力做到以下两点：

  1. 映射函数f(x)能够将N个元素尽量平均分配到M个桶中。每个桶中就有[N/M]个元素了。
  2. 尽量增加桶的个数。极限情况下，每个桶只有一个元素，这样就不需要进行桶内的排序操作。

我们并不能无限的扩大桶的个数，所以桶排序的应用范围较窄。

3、算法描述：

假设有数组{32,17,99,20,54,78,32,29,21,70}，利用桶排序进行升序排列。

  1. 数组中所有元素都是10<arr[i]<100的，我们设置10个桶，编号0~9，然后确定映射函数为f(i)=arr[i]/10，这样的话第一个关键字32将定位到第3个桶中，32/10=3。依次将所有的元素放入桶中。
  2. 对于单个桶中有多个元素的情况，比如，20,29,21都当在第2个桶中，对这个桶进行快速排序，这样桶中的元素就处理完成了。
  3. 所有桶内排序完成后，将元素顺序输出。


4、Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.ArrayList;
import java.util.Iterator;
/**
 * 桶排序
 * @author lizhen
 */
public class BucketSort {
	/**
	 * 升序排序  
	 * @param arr 数组{32,17,99,20,54,78,32,29,21,70}
	 */
	public void bucketSort(int[] arr){
		//生成一个长度为10的桶 ,10个桶为数组，每个桶为一个线性表Arrylist
		ArrayList<Integer>[] list = new ArrayList[10];
		//将数组arr放入这个10个桶内
		for(int i=0;i<arr.length;i++){
			//定义映射函数f(x)=x/10
			int temp = arr[i]/10;
			if(null==list[temp]){
				//首次往桶中增加数据时要new Arraylist对象。				
				list[temp] = new ArrayList<Integer>();
			}
			//将arr[i]添加到桶中
			list[temp].add(arr[i]);
		}
		/*
		 * 运行至此处，已经将所有数据放入桶中，调试查看list的值如下：
		 * [null, [17], [20, 29, 21], [32, 32], null, [54], null, [78, 70], null, [99]]
		 */
		//对每个桶内元素排序。
		for(int j=0;j<list.length;j++){
			ArrayList<Integer> tempList = list[j];
			//判断是否多于一个元素
			if(tempList==null||tempList.size()<=1){
				continue;
			}else{
				//多于一个的使用快排排序
				quciksort(tempList,0,tempList.size()-1);
			}
		}
		/*
		 * 运行至此，所有桶内元素都已经排好序，调试查看：
		 * [null, [17], [20, 21, 29], [32, 32], null, [54], null, [70, 78], null, [99]]
		 */
		//将templist与arr合并。
		int count = 0;//数组游标
		for(int k=0;k<list.length;k++){
			if(null!=list[k]){
				//遍历每一个桶里的list，顺序合并至数组
				Iterator iterator = list[k].iterator();
				while(iterator.hasNext()){
					arr[count] = (Integer) iterator.next();
					count++;
				}
			}
		}
	}
	//使用快速排序对桶内数据进行排序  [20, 29, 21]
	private void quciksort(ArrayList<Integer> tempList,int left,int right) {
		if(left>=right)
			return;
		
		int i = left;
		int j = right;
		int temp = tempList.get(left);
		while(i<j){
			while(tempList.get(j)>=temp && i<j){
				j--;
			}
			while(tempList.get(i)<=temp && i<j){
				i++;
			}
			if(i<j){
				int tempC = tempList.get(j);
				tempList.set(j, tempList.get(i));
				tempList.set(i, tempC);
			}
		}
		//交换
		tempList.set(left, tempList.get(i));
		tempList.set(i, temp);
		
		quciksort(tempList,left,i-1);
		quciksort(tempList,i+1,right);
	}
}

5、效率分析：