本文共 2121 字,大约阅读时间需要 7 分钟。
桶排序,简单来说就是将待排序序列,按照序列值的大小划分成几个桶,分别对每组进行排序,排完序之后再按照一定的顺序合并所有的桶,即排序完成。
7 | 12 | 56 | 23 | 19 | 33 | 35 | 42 | 42 | 2 | 8 | 22 | 39 | 26 | 17 |
[2,13) | [13,24) | [24,35) | [35,46) | [46,57) |
2,7,8,12 | 17,19,22,23 | 26,33 | 35,39,42,42 | 56 |
2 | 7 | 8 | 12 | 17 | 19 | 22 | 23 | 26 | 33 | 35 | 39 | 42 | 42 | 56 |
public class BucketSort { public static void bucketSort(int[] arr) { if (arr == null || arr.length == 0) { return; } int len = arr.length; // 根据原始序列的长度,设置桶的数量。这里假设每个桶放最多放4个元素 int bucketCount = len / 4; // 遍历原始序列,找出最大值和最小值 int min = 0, max = 0; for (int i = 0; i < len; i++) { if (arr[i] > max) { max = arr[i]; } else if (arr[i] < min) { min = arr[i]; } } // 每个桶的数值范围 int range = (max - min + 1) / bucketCount; int[][] buckets = new int[bucketCount][]; // 遍历原始序列 for (int i = 0; i < len; i++) { int val = arr[i]; // 计算当前值属于哪个桶 int bucketIndex = (int) Math.floor((val - min) / range); // 向桶中添加元素 buckets[bucketIndex] = appendItem(buckets[bucketIndex], val); } // 最后合并所有的桶 int k = 0; for (int[] b : buckets) { if (b != null) { for (int i = 0; i < b.length; i++) { arr[k++] = b[i]; } } } } private static int[] appendItem(int[] bucketArr, int val) { if (bucketArr == null || bucketArr.length == 0) { return new int[]{val}; } // 拷贝一下原来桶的序列,并增加一位 int[] arr = Arrays.copyOf(bucketArr, bucketArr.length + 1); // 这里使用插入排序,将新的值val插入到序列中 for (int i = bucketArr.length - 1; i >= 0; i--) { // 从新序列arr的倒数第二位开始向前遍历(倒数第一位是新增加的空位,还没有值) // 如果当前序列值大于val,那么向后移位 if (arr[i] > val) { arr[i + 1] = arr[i]; } else { arr[i + 1] = val; break; } } return arr; }}
桶排序的平均时间复杂度为 O ( n + k ) O(n+k) O(n+k),最坏的情况为 O ( n 2 ) O(n^2) O(n2),空间复杂度为 O ( n + k ) O(n + k) O(n+k)。
转载地址:http://uayin.baihongyu.com/