这是本系列的最后一篇文章，接前文
8 计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
算法描述
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
动图演示
代码实现
1public class CountingSort implements IArraySort {
2
3 @Override
4 public int[] sort(int[] sourceArray) throws Exception {
5 // 对 arr 进行拷贝，不改变参数内容
6 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8 int maxValue = getMaxValue(arr);
9
10 return countingSort(arr, maxValue);
11 }
12
13 private int[] countingSort(int[] arr, int maxValue) {
14 int bucketLen = maxValue + 1;
15 int[] bucket = new int[bucketLen];
16
17 for (int value : arr) {
18 bucket[value]++;
19 }
20
21 int sortedIndex = 0;
22 for (int j = 0; j < bucketLen; j++) {
23 while (bucket[j] > 0) {
24 arr[sortedIndex++] = j;
25 bucket[j]--;
26 }
27 }
28 return arr;
29 }
30
31 private int getMaxValue(int[] arr) {
32 int maxValue = arr[0];
33 for (int value : arr) {
34 if (maxValue < value) {
35 maxValue = value;
36 }
37 }
38 return maxValue;
39 }
40
41}
42
43```java
44
45计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
46
47### 9 桶排序（Bucket Sort）
48
49桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
50
51为了使桶排序更加高效，我们需要做到这两点：
52
53- 在额外空间充足的情况下，尽量增大桶的数量
54
55- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
56
57同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
58
59#### 算法描述
60
61- 设置一个定量的数组当作空桶；
62
63- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
64
65- 对每个不是空的桶进行排序；
66
67- 从不是空的桶里把排好序的数据拼接起来。
68
69#### 动图演示
70
71
72
73#### 代码实现
74
75```cs
76public class BucketSort implements IArraySort {
77
78 private static final InsertSort insertSort = new InsertSort();
79
80 @Override
81 public int[] sort(int[] sourceArray) throws Exception {
82 // 对 arr 进行拷贝，不改变参数内容
83 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
84
85 return bucketSort(arr, 5);
86 }
87
88 private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
89 if (arr.length == 0) {
90 return arr;
91 }
92
93 int minValue = arr[0];
94 int maxValue = arr[0];
95 for (int value : arr) {
96 if (value < minValue) {
97 minValue = value;
98 } else if (value > maxValue) {
99 maxValue = value;
100 }
101 }
102
103 int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
104 int[][] buckets = new int[bucketCount][0];
105
106 // 利用映射函数将数据分配到各个桶中
107 for (int i = 0; i < arr.length; i++) {
108 int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
109 buckets[index] = arrAppend(buckets[index], arr[i]);
110 }
111
112 int arrIndex = 0;
113 for (int[] bucket : buckets) {
114 if (bucket.length <= 0) {
115 continue;
116 }
117 // 对每个桶进行排序，这里使用了插入排序
118 bucket = insertSort.sort(bucket);
119 for (int value : bucket) {
120 arr[arrIndex++] = value;
121 }
122 }
123
124 return arr;
125 }
126
127 /**
128 * 自动扩容，并保存数据
129 *
130 * @param arr
131 * @param value
132 */
133 private int[] arrAppend(int[] arr, int value) {
134 arr = Arrays.copyOf(arr, arr.length + 1);
135 arr[arr.length - 1] = value;
136 return arr;
137 }
138
139}
140
141```java
142
143什么时候最快?
144
145当输入的数据可以均匀的分配到每一个桶中。
146
147什么时候最慢?
148
149当输入的数据被分配到了同一个桶中。
150
151### 10 基数排序（Radix Sort）
152
153基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
154
155基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
156
157#### 算法描述
158
159- 取得数组中的最大数，并取得位数；
160
161- arr为原始数组，从最低位开始取每个位组成radix数组；
162
163- 对radix进行计数排序（利用计数排序适用于小范围数的特点）
164
165#### 动图演示
166
167
168
169#### 代码实现
170
171```cs
172/**
173 * 基数排序
174 * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
175 */
176public class RadixSort implements IArraySort {
177
178 @Override
179 public int[] sort(int[] sourceArray) throws Exception {
180 // 对 arr 进行拷贝，不改变参数内容
181 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
182
183 int maxDigit = getMaxDigit(arr);
184 return radixSort(arr, maxDigit);
185 }
186
187 /**
188 * 获取最高位数
189 */
190 private int getMaxDigit(int[] arr) {
191 int maxValue = getMaxValue(arr);
192 return getNumLenght(maxValue);
193 }
194
195 private int getMaxValue(int[] arr) {
196 int maxValue = arr[0];
197 for (int value : arr) {
198 if (maxValue < value) {
199 maxValue = value;
200 }
201 }
202 return maxValue;
203 }
204
205 protected int getNumLenght(long num) {
206 if (num == 0) {
207 return 1;
208 }
209 int lenght = 0;
210 for (long temp = num; temp != 0; temp /= 10) {
211 lenght++;
212 }
213 return lenght;
214 }
215
216 private int[] radixSort(int[] arr, int maxDigit) {
217 int mod = 10;
218 int dev = 1;
219
220 for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
221 // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
222 int[][] counter = new int[mod * 2][0];
223
224 for (int j = 0; j < arr.length; j++) {
225 int bucket = ((arr[j] % mod) / dev) + mod;
226 counter[bucket] = arrayAppend(counter[bucket], arr[j]);
227 }
228
229 int pos = 0;
230 for (int[] bucket : counter) {
231 for (int value : bucket) {
232 arr[pos++] = value;
233 }
234 }
235 }
236
237 return arr;
238 }
239
240 /**
241 * 自动扩容，并保存数据
242 *
243 * @param arr
244 * @param value
245 */
246 private int[] arrayAppend(int[] arr, int value) {
247 arr = Arrays.copyOf(arr, arr.length + 1);
248 arr[arr.length - 1] = value;
249 return arr;
250 }
251}
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
关注公众号 获取更多精彩内容