桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:

  1. 在额外空间充足的情况下,尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。

什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

什么时候最慢

当输入的数据被分配到了同一个桶中。

1. 算法分析

桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。

2. 算法步骤

  1. 设置一个定量的数组当作空桶;
  2. 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  3. 对每个不是空的桶进行排序;
  4. 从不是空的桶里把排好序的数据拼接起来。

3. 动图演示

动图演示

4. 代码实现

1. JavaScript 代码实现

  1. function bucketSort(arr, bucketSize) {
  2. if (arr.length === 0) {
  3. return arr;
  4. }
  5. var i;
  6. var minValue = arr[0];
  7. var maxValue = arr[0];
  8. for (i = 1; i < arr.length; i++) {
  9. if (arr[i] < minValue) {
  10. minValue = arr[i]; // 输入数据的最小值
  11. } else if (arr[i] > maxValue) {
  12. maxValue = arr[i]; // 输入数据的最大值
  13. }
  14. }
  15. //桶的初始化
  16. var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5
  17. bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  18. var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  19. var buckets = new Array(bucketCount);
  20. for (i = 0; i < buckets.length; i++) {
  21. buckets[i] = [];
  22. }
  23. //利用映射函数将数据分配到各个桶中
  24. for (i = 0; i < arr.length; i++) {
  25. buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
  26. }
  27. arr.length = 0;
  28. for (i = 0; i < buckets.length; i++) {
  29. insertionSort(buckets[i]); // 对每个桶进行排序,这里使用了插入排序
  30. for (var j = 0; j < buckets[i].length; j++) {
  31. arr.push(buckets[i][j]);
  32. }
  33. }
  34. return arr;
  35. }

2. Java 代码实现

  1. public class BucketSort implements IArraySort {
  2. private static final InsertSort insertSort = new InsertSort();
  3. @Override
  4. public int[] sort(int[] sourceArray) throws Exception {
  5. // 对 arr 进行拷贝,不改变参数内容
  6. int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  7. return bucketSort(arr, 5);
  8. }
  9. private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
  10. if (arr.length == 0) {
  11. return arr;
  12. }
  13. int minValue = arr[0];
  14. int maxValue = arr[0];
  15. for (int value : arr) {
  16. if (value < minValue) {
  17. minValue = value;
  18. } else if (value > maxValue) {
  19. maxValue = value;
  20. }
  21. }
  22. int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
  23. int[][] buckets = new int[bucketCount][0];
  24. // 利用映射函数将数据分配到各个桶中
  25. for (int i = 0; i < arr.length; i++) {
  26. int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
  27. buckets[index] = arrAppend(buckets[index], arr[i]);
  28. }
  29. int arrIndex = 0;
  30. for (int[] bucket : buckets) {
  31. if (bucket.length <= 0) {
  32. continue;
  33. }
  34. // 对每个桶进行排序,这里使用了插入排序
  35. bucket = insertSort.sort(bucket);
  36. for (int value : bucket) {
  37. arr[arrIndex++] = value;
  38. }
  39. }
  40. return arr;
  41. }
  42. /**
  43. * 自动扩容,并保存数据
  44. *
  45. * @param arr
  46. * @param value
  47. */
  48. private int[] arrAppend(int[] arr, int value) {
  49. arr = Arrays.copyOf(arr, arr.length + 1);
  50. arr[arr.length - 1] = value;
  51. return arr;
  52. }
  53. }

3. PHP 代码实现

  1. function bucketSort($arr, $bucketSize = 5)
  2. {
  3. if (count($arr) === 0) {
  4. return $arr;
  5. }
  6. $minValue = $arr[0];
  7. $maxValue = $arr[0];
  8. for ($i = 1; $i < count($arr); $i++) {
  9. if ($arr[$i] < $minValue) {
  10. $minValue = $arr[$i];
  11. } else if ($arr[$i] > $maxValue) {
  12. $maxValue = $arr[$i];
  13. }
  14. }
  15. $bucketCount = floor(($maxValue - $minValue) / $bucketSize) + 1;
  16. $buckets = array();
  17. for ($i = 0; $i < count($buckets); $i++) {
  18. $buckets[$i] = [];
  19. }
  20. for ($i = 0; $i < count($arr); $i++) {
  21. $buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
  22. }
  23. $arr = array();
  24. for ($i = 0; $i < count($buckets); $i++) {
  25. $bucketTmp = $buckets[$i];
  26. sort($bucketTmp);
  27. for ($j = 0; $j < count($bucketTmp); $j++) {
  28. $arr[] = $bucketTmp[$j];
  29. }
  30. }
  31. return $arr;
  32. }