一.桶排序
算法原理
桶排序 (箱排序)的原理是将待排序序列分到有限数量的桶里面，然后对每个桶再分别排序（可以使用其它的排序算法或者是递归使用桶排序算法），最后将各个桶中的数据有序的合并起来成为一个整体有序的序列。
排序过程：
1.假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
2.将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
3.将各个桶中的数据有序的合并起来
实例分析
设有数组 array = [29, 25, 3, 49, 9, 37, 21, 43]，那么数组中最大数为 49，先设置 5 个桶，那么每个桶可存放数的范围为：09、1019、2029、3039、40~49，然后分别将这些数放人自己所属的桶，如下图：
然后，分别对每个桶里面的数进行排序，或者在将数放入桶的同时用插入排序进行排序。最后，将各个桶中的数据有序的合并起来，如下图：
Java实现
/**
* 桶排序
*
* @param arr
*/
public static void bucketSort(int[] arr) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<>());
}
for (int i = 0; i < arr.length; i++) {
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
for (int i = 0; i < bucketArr.size(); i++) {
Collections.sort(bucketArr.get(i));
}
int index = 0;
for (ArrayList<Integer> list : bucketArr) {
for (Integer integer : list) {
arr[index ++] = integer;
}
}
}
效率分析
1.时间复杂度：O(m+n)
2.空间复杂度：O(m+n)
适用情况分析
适用于序列比较均匀的情况，否则会很耗空间。
或者特殊的场景，例如需要对一个公司的员工的年龄进行排序，年龄的范围为1-120，此时就可以开辟120个桶进行统计排序。
另，桶排序的瓶颈主要是桶数量的选择。
另此算法为稳定的排序算法。
二.哈希桶排序（概念都是自定义的）
算法原理
排序算法主要是用分治法，用哈希函数对序列进行划分，最后使用其它的排序算法或者递归使用哈希排序进行排序从而得到一个整体有序的序列。下面先介绍几个自定义的概念：
1.哈希桶排序：因为本算法是使用了哈希函数把序列划分到对应的桶里面，所以本排序算法取名为哈希桶排序。
2.哈希桶因子（hashFactor）：hashFactor = （max - min） / length
计算公式如上式，当结果小于等于0的时候再做特殊处理，据此因子进行桶的划分。
实例分析
设有数组 array = [10011, 10001, 16, 14, 12, 10000, 10, 10002, 10003, 1]，那么数组中最大值max = 10011，最小值min = 1，哈希桶因子hashFactor = （10011 - 1） / 10 = 1001。对数组进行划分，10011 / 1001 = 10，所以10011放在keywei10的桶里面；10001 / 1001 = 9， 所以10001放在key为9的桶里面，以此类推，最后得到的桶的情况为：{0=[1, 10, 12, 14, 16], 9=[10000, 10001, 10002, 10003], 10=[10011]}。再分别对每个桶进行排序即可。
Java实现
/**
* 哈希桶排序
*
* @param arr
*/
public static void hashSort(int[] arr) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int consult = (max - min) / arr.length;
if (consult <= 0) {
if (arr.length < 1000) { // 数据比较小的时候整个数列直接排序
consult = max;
} else { // 数据比较大的时候分为11个列表
consult = max / 10;
}
}
TreeSet<Integer> set = new TreeSet();
for (int i = 0; i < arr.length; i++) {
set.add(arr[i] / consult);
}
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>(set.size());
for (Integer key : set) {
map.put(key, new ArrayList<>());
}
for (int i = 0; i < arr.length; i++) {
map.get(Integer.valueOf(arr[i] / consult)).add(Integer.valueOf(arr[i]));
}
Iterator<Map.Entry<Integer, ArrayList<Integer>>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, ArrayList<Integer>> entry = it.next();
Collections.sort(entry.getValue());
}
int index = 0;
it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, ArrayList<Integer>> entry = it.next();
for (Integer num : entry.getValue()) {
arr[index ++] = num;
}
}
}
效率分析
1.时间复杂度：O(m+n)
2.空间复杂度：O(m+n)
适用情况分析
此算法与桶排序对比，主要是通过哈希建桶的方式减少了空间的消耗，对序列进行了一个归约，时间上跟桶排序相当。
使用与序列的最小最大值相差比较大同时又出现在某一个取值区间的集聚的情况。
另此算法为稳定的排序算法。
网友评论