计数排序
应用范围
- 局限于在一定范围内的整数类型进行排序
实现原理
- 获取最大最小值 （优化范围太大）
- 创建和原数组大小相同的结果数组容器 (收集排序后的容器)
- 根据最值间距创建对应大小的统计数组
- 遍历原数组然后对应下标++ （构建统计数组）
- 将统计数组转化为统计和数组 (实现稳定排序)
- 逆序遍历原数组填充结果数组，并给匹配的统计和数组的下标减1
实现代码如下
/**
* 计数排序 -> 对一定范围内的整数进行排序
* 思路：
* - 获取数组中的最大值
* - 构造0 -> 最大值的数组
* - 遍历数字是多少对应下标+1
* - 遍历数组，数字多少则输出多少次对应下标
* <p>
* 优化：
* - 考虑值的最小值，需要获取最大值和最小值的一段间距充当统计数组的大小
* - 对分数段相同的如何进行稳定排序？
* - 对统计数组进行改造，对应下标的值改为前面所有值的和，这么做是为了值的具体排名，
* 然后在元素进行遍历的时候就可以通过对该值-1来分辨相同元素前后了
* <p>
* <p>
* 时间复杂度是 ： O(n+m) -> n: 原数据大小 m: 最值直接的间距
* 空间复杂度： 不考虑结果容器为O(m)
*
* @param arr
*/
public static void countingSort(int[] arr) {
int[] result = new int[arr.length];
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
max = max < arr[i] ? arr[i] : max;
min = min > arr[i] ? arr[i] : min;
}
//获取间距
int space = max - min;
int[] tmp = new int[space + 1];
for (int i : arr) {
tmp[i - min]++;
}
//对统计数组进行变形,目标是为方便获取相同数据的顺序
for (int i = 0; i < tmp.length - 1; i++) {
tmp[i + 1] += tmp[i];
}
//遍历原数据
for (int i : arr) {
//填充到结果数组tmp[i-min] -> 表示排序位置
result[tmp[i - min] - 1] = i;
//设置之后统计数-1，确定后面相同元素的位置
tmp[i - min]--;
}
System.out.println(Arrays.toString(result));
}
桶排序
时间复杂度 O（n），当桶分配不均匀时会降低到 O(nlogn) ，空间复杂度O (n)
- 为了优化计数排序的整数，以及范围问题，将容器化分到多个区间桶中
- 桶中元素各自排序
- 按顺序遍历即可
public static void bucketSort(double[] arr) {
//获取最大值最小值
double max = arr[0];
double min = arr[0];
for (double v : arr) {
max = max < v ? v : max;
min = min > v ? v : min;
}
//计算区间跨度
double d = max - min;
//桶数量，默认为原数组数量
int bucketNum = arr.length;
//初始化桶
ArrayList<LinkedList<Double>> bucketList = Lists.newArrayList();
for (int i = 0; i < bucketNum; i++) {
bucketList.add(Lists.newLinkedList());
}
//将元素放入对应桶中
for (double v : arr) {
//根据比例获取桶编号，索引从0开始，所以为bucketNum-1
int num = (int) ((v - min) / d * (bucketNum - 1));
//加入桶
bucketList.get(num).add(v);
}
//对桶进行依次排序
for (int i = 0; i < bucketNum; i++) {
Collections.sort(bucketList.get(i));
}
//顺序遍历
for (LinkedList<Double> doubles : bucketList) {
for (Double aDouble : doubles) {
System.out.print(aDouble + " ");
}
}
}
