桶排序-超级容易上手的一种排序

桶排序

其实就是划分区间，以区间为桶，每个桶贴个范围(下面那个59是50，写错了)

以每个自己的桶范围，放入范围的数字就可以了

那么如何确定我们的桶范围还有桶数组的大小呢？

首先我们传进来 arr.length=7

我们可以通过最大值最小值确定桶数组长度

// 计算桶的数量
int bucketNum = (max - min) / arr.length + 1;

算出来（50-12）/7+1=6,所以我们可以确立一个长度为6的桶数组，但是一个数组位置肯定放不下这么多数据

所以我们可以在数组上纵向扩展一个桶，这个跟ConcurrentHashMap类似，确定了桶之后分段加锁比较高效

 ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }

桶已经准备好了，该如何放数据呢

我们只需要让当前数组值减去最小值然后除数组长度，就可以得到他的桶下标了，因为我们是最大值和最小值确定的数组长度，所以当前数组值减去最小值无论怎么算都会在所有桶数组中哪一个下标

    // 将每个元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }java

对应桶有数据了，该开始主要操作了，排序大法好

    // 对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));

每个桶里面排序完这样我们取的时候只要按顺序取就好了

我们开始取数组，即可完成桶排序

// 将桶中的元素赋值到原序列
	int index = 0;
    //这个bucketArr其实就是桶数组的长度
	for(int i = 0; i < bucketArr.size(); i++){
        //每个桶的容量里面的数据取出，并且赋值给原数组
		for(int j = 0; j < bucketArr.get(i).size(); j++){
			arr[index++] = bucketArr.get(i).get(j);
		}
	}  

完成了排序，发现这个排序最主要就是确立下标和桶数组范围，其它的操作都很简单

时间复杂度

对于待排序序列大小为 N，共分为 M 个桶，主要步骤有：

• N 次循环，将每个元素装入对应的桶中
• M 次循环，对每个桶中的数据进行排序（平均每个桶有 N/M 个元素）

一般使用较为快速的排序算法，时间复杂度为 O(NlogN)O(NlogN) O(NlogN)O(NlogN)，实际的桶排序过程是以链表形式插入的

完整代码实现

package 桶排序;

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

public class tong {
	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<Integer>());
	    }
	    
	    // 将每个元素放入桶
	    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(int i = 0; i < bucketArr.size(); i++){
			for(int j = 0; j < bucketArr.get(i).size(); j++){
				arr[index++] = bucketArr.get(i).get(j);
			}
		}  
	}

}

package 桶排序;
import java.util.Arrays;
public class Test {
	//测试
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
          int[] a= {9,1,2,5,7,4,8,6,3,5};
          System.out.println(Arrays.toString(a));
          tong.bucketSort(a);
          System.out.println(Arrays.toString(a));
         //[9, 1, 2, 5, 7, 4, 8, 6, 3, 5]
         //[1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
	}
}

必背