话不多说！程序员必学的十大算法( 五 ) _为什么

25 for (int j = temp[i]; j > 0; j--) {
26 arr[k++] = i + min;
27 }
28 }
29 return arr;
30 }
31}
9、桶排序
桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。
之后每个桶里面的数据就是有序的了，我们在进行合并汇总。
为方便理解我还准备了图片：

文章插图
如果还是不懂的话我还给你准备了优质的文章讲解：什么是桶排序？
代码如下：
1public class BucketSort {
2 public static int[] BucketSort(int[] arr) {
3 if(arr == null || arr.length < 2) return arr;
4
5 int n = arr.length;
6 int max = arr[0];
7 int min = arr[0];
8 // 寻找数组的最大值与最小值
9 for (int i = 1; i < n; i++) {
10 if(min > arr[i])
11 min = arr[i];
12 if(max < arr[i])
13 max = arr[i];
14 }
15 //和优化版本的计数排序一样，弄一个大小为 min 的偏移值
16 int d = max - min;
17 //创建 d / 5 + 1 个桶，第 i 桶存放 5*i ~ 5*i+5-1范围的数
18 int bucketNum = d / 5 + 1;
19 ArrayList
20 //初始化桶
21 for (int i = 0; i < bucketNum; i++) {
22 bucketList.add(new LinkedList
23 }
24 //遍历原数组，将每个元素放入桶中
25 for (int i = 0; i < n; i++) {
26 bucketList.get((arr[i]-min)/d).add(arr[i] - min);
27 }
28 //对桶内的元素进行排序，我这里采用系统自带的排序工具
29 for (int i = 0; i < bucketNum; i++) {
30 Collections.sort(bucketList.get(i));
31 }
32 //把每个桶排序好的数据进行合并汇总放回原数组
33 int k = 0;
34 for (int i = 0; i < bucketNum; i++) {
35 for (Integer t : bucketList.get(i)) {
36 arr[k++] = t + min;
37 }
38 }
39 return arr;
40 }
41}
性质：1、时间复杂度：O(n+k) 2、空间复杂度：O(n+k) 3、稳定排序 4、非原地排序
注：k 表示桶的个数，下同
10、基数排序
基数排序的排序思路是这样的：先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小……
排到最后，就是一组有序的元素了。不过，他在以某位数进行排序的时候，是用“桶”来排序的。
由于某位数（个位/十位….，不是一整个数）的大小范围为0-9，所以我们需要10个桶，然后把具有相同数值的数放进同一个桶里，之后再把桶里的数按照0号桶到9号桶的顺序取出来，这样一趟下来，按照某位数的排序就完成了
为方便理解我还准备了动图：

文章插图
如果还是不懂的话我还给你准备了优质的文章讲解：为什么说O(n)复杂度的基数排序没有快速排序快？
代码如下：
1public class RadioSort {
2
3 public static int[] radioSort(int[] arr) {
4 if(arr == null || arr.length < 2) return arr;
5
6 int n = arr.length;
7 int max = arr[0];
8 // 找出最大值
9 for (int i = 1; i < n; i++) {
10 if(max < arr[i]) max = arr[i];
11 }
12 // 计算最大值是几位数
13 int num = 1;
14 while (max / 10 > 0) {
15 num++;
16 max = max / 10;
17 }
18 // 创建10个桶
19 ArrayList
20 //初始化桶
21 for (int i = 0; i < 10; i++) {
22 bucketList.add(new LinkedList
23 }
24 // 进行每一趟的排序，从个位数开始排
25 for (int i = 1; i <= num; i++) {
26 for (int j = 0; j < n; j++) {
27 // 获取每个数最后第 i 位是数组
28 int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10;
29 //放进对应的桶里
30 bucketList.get(radio).add(arr[j]);
31 }
32 //合并放回原数组
33 int k = 0;
34 for (int j = 0; j < 10; j++) {
35 for (Integer t : bucketList.get(j)) {
36 arr[k++] = t;
37 }
38 //取出来合并了之后把桶清光数据
39 bucketList.get(j).clear();
40 }
41 }
42 return arr;
43 }
44}
性质：1、时间复杂度：O(kn) 2、空间复杂度：O(n+k) 3、稳定排序 4、非原地排序
总结
用一张图汇总了10大排序算法的性质