写在前面
十大经典排序算法总结(冒泡排序)
十大经典排序算法总结(快速排序)
十大经典排序算法总结(归并排序)
十大经典排序算法总结(选择排序)
十大经典排序算法总结(插入排序)
十大经典排序算法总结(堆排序)
十大经典排序算法总结(希尔排序)
十大经典排序算法总结(计数排序)
十大经典排序算法总结(桶排序)
十大经典排序算法总结(基数排序)
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排
示意图
package com.zhuang.algorithm; import java.util.ArrayList; import java.util.*; /** * @Classname BucketSort * @Description 桶排序 * @Date 2021/6/13 19:07 * @Created by dell */ public class BucketSort { public static void main(String[] args) { int[] arr = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50}; bucketSort(arr); System.out.println("桶排序以后的序列为:"); System.out.println(Arrays.toString(arr)); } public static void bucketSort(int[] arr) { //最大最小值 int max = arr[0]; int min = arr[0]; int len = arr.length; for (int i = 0; i < len; i++) { if (arr[i] > max) { max = arr[i]; } else if (arr[i] < min) { max = arr[i]; } } //最大值和最小值得差 int diff = max - min; //桶列表 ArrayList<ArrayList<Integer>> list = new ArrayList<>(); for (int i = 0; i < len; i++) { list.add(new ArrayList<>()); } //每个桶的存数区间 float section = (float) diff / (float) (len - 1); //数据入桶 for (int i = 0; i < len; i++) { //当前数除以区间得出存放桶的位置,减1得出桶的下标 int num = (int) ((arr[i] / section) - 1); if (num < 0) { num = 0; } list.get(num).add(arr[i]); } //桶内排序 for (int i = 0; i < list.size(); i++) { Collections.sort(list.get(i)); } //写入原数组 int index = 0; for (ArrayList<Integer> arrayList : list) { for (Integer integer : arrayList) { arr[index] = integer; index++; } } } }
或者下列方法也可以
package com.zhuang.algorithm; import java.util.ArrayList; import java.util.*; /** * @Classname BucketSort * @Description 桶排序 * @Date 2021/6/13 19:07 * @Created by dell */ public class BucketSort { public static void main(String[] args) { int[] arr = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50}; bucketSort(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<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)); } System.out.println(bucketArr.toString()); } }
桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大
桶排序可用于最大最小值相差较大的数据情况,但桶排序要求数据的分布必须均匀,否则可能导致数据都集中到一个桶中
写在最后