十大经典排序算法动画与解析,看我就够了!(配代码完全版) (5)

image

image

8.3 参考代码 1//Java 代码实现
2public class CountingSort implements IArraySort {
3
4    @Override
5    public int[] sort(int[] sourceArray) throws Exception {
6        // 对 arr 进行拷贝,不改变参数内容
7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
8
9        int maxValue = getMaxValue(arr);
10
11        return countingSort(arr, maxValue);
12    }
13
14    private int[] countingSort(int[] arr, int maxValue) {
15        int bucketLen = maxValue + 1;
16        int[] bucket = new int[bucketLen];
17
18        for (int value : arr) {
19            bucket[value]++;
20        }
21
22        int sortedIndex = 0;
23        for (int j = 0; j < bucketLen; j++) {
24            while (bucket[j] > 0) {
25                arr[sortedIndex++] = j;
26                bucket[j]--;
27            }
28        }
29        return arr;
30    }
31
32    private int getMaxValue(int[] arr) {
33        int maxValue = arr[0];
34        for (int value : arr) {
35            if (maxValue < value) {
36                maxValue = value;
37            }
38        }
39        return maxValue;
40    }
41
42}
9. 桶排序 9.1 算法步骤

设置固定数量的空桶。

把数据放到对应的桶中。

对每个不为空的桶中数据进行排序。

拼接不为空的桶中数据,得到结果

9.2 动画演示

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wsfpsj.html