排序算法--桶排序的原理及案例(Java)

概述

  • 桶排序，又叫箱排序，是一种比较常见的排序算法。其主要思想是分治思想，将大问题化成小问题。是将数组里的数据分配成几个区间中，然后再对区间里的数据分别排序，最后依次把各个区间中的记录列出来即可得到有序序列。

原理步骤

  • 假设现在有一个数组 arr = [19, 27, 35, 43, 31, 22, 54, 66, 78, 2, 65, 56, 3, 1, 17, 20, 44, 7]
  • 观察将要排序的数组中的元素大小分布范围为（0，79），于是我们可以分成几个存储区间，例如:（0，19），（20，39），（40，59），（60，79），这些区间也就是桶，桶的数量，范围可以按照需要自行定义。
  • 然后将数组里的数据按照大小分配到对应的桶中。
  • 对各个桶内的数据进行排序，最后按顺序输出，即可得到大数组的排序结果。
    在这里插入图片描述

Java代码

  • Java代码:
public class BucketSort {
    public void bucketSort(int[] nums) {
        int n = nums.length;
        int min = nums[0], max = nums[0];
        // 找出数组中的最大最小值
        for (int i = 1; i < n; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        // 设置每个桶存储数的范围大小，可以根据需求指定。
        // 为使得数尽量均匀地分布在各个桶中，所以这里根据数据范围设置，范围大小保证最少存储一个
        int size = (max - min) / n + 1;
        // 设置桶的个数，与每个桶的范围有关，保证桶的个数至少为1
        int count = (max - min) / size + 1; 
        List<Integer>[] buckets = new List[count]; // 声明count个数组用来表示桶
        for (int i = 0; i < count; i++) {
            buckets[i] = new ArrayList<>();
        }
        // 扫描一遍数组，将符合范围的数放进桶里
        for (int i = 0; i < n; i++) {
            int idx = (nums[i] - min) / size;
            buckets[idx].add(nums[i]);
        }
        // 对各个桶中的数进行排序，这里用库函数快速排序，也可以选择其他自定义的算法
        for (int i = 0; i < count; i++) {
            buckets[i].sort(null); // 默认是按从小打到排序
        }
        // 依次将各个桶中的数据放入返回数组中，得到排序后的结果数组
        int index = 0;
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                nums[index++] = buckets[i].get(j);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {19, 27, 35, 43, 31, 22, 54, 66, 78, 2, 65, 56, 3, 1, 17, 20, 44, 7};
        System.out.print("排序前的数组：");
        Arrays.stream(nums).forEach(x-> System.out.print(x+" "));
        BucketSort bucketSort = new BucketSort();
        bucketSort.bucketSort(nums);
        System.out.print("\n排序后的数组：");
        Arrays.stream(nums).forEach(x-> System.out.print(x+" "));
    }
}

  • 运行main方法，测试结果:
    在这里插入图片描述

  • 桶排序的时间复杂度

假设桶排序的元素分布相对平均，共n个元素，分为m个桶，桶内排序算法任选一个O（nlogn）的算法，那么全部桶的计算量为：
O（n）+ O（m*（n/m）*log(n/m)）= O（n）+ O（n * log（n/m）），若n接近于m，则该式子可近似于O（n）
桶排序是空间换时间的一种体现，在空间充足的情况下，增加桶的数量，可以使算法更高效。

运用案例

  • 题目: 找出数组中差值最小的两个元素 要求时间复杂度为O(n)
  • 因为要求时间复杂度为O（n），所以使用桶排序，以下为java代码：
    public class MinDiff {
   public static void main(String[] args) {
       int[] arr = {107, 1, 41, 146, 59, 12, 26, 18, 137,100};
       int minDiff = findMinDiff(arr);
       System.out.println("数组最接近的两个元素的差值为："+minDiff);
   }

   public static int findMinDiff(int[] arr) {
       int n = arr.length;
       if (n < 2) {
           return -1;
       }
       //找到最大值和最小值
       int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
       for (int i = 0; i < n; i++) {
           if (arr[i] > maxVal) {
               maxVal = arr[i];
           }
           if (arr[i] < minVal) {
               minVal = arr[i];
           }
       }
       //计算桶的个数和高度,这里的宽度我们指定为1，增加桶的个数，使得时间复杂度更低
       int bucketWidth = 1;
       int bucketCount = (maxVal - minVal)/bucketWidth + 1;
       //初始化桶
       int[][] buckets = new int[bucketCount][bucketWidth];
       int[] bucketSizes = new int[bucketCount];
       //将元素放到对应的桶中
       for (int i = 0; i < n; i++) {
           int index = (arr[i] - minVal) / bucketWidth;
           buckets[index][bucketSizes[index]++] = arr[i];
       }
       //对每个桶进行排序
       for (int i = 0; i < bucketCount; i++) {
           if (bucketSizes[i] > 0) {
               Arrays.sort(buckets[i], 0, bucketSizes[i]);
           }
       }
       //计算相邻桶的最小差值
       int minDiff = Integer.MAX_VALUE;
       int prevMax = buckets[0][0];
       for (int i = 1; i < bucketCount; i++) {
           if (bucketSizes[i] == 0) {
               continue;
           }
           int currMin = buckets[i][0];
           int diff = currMin - prevMax;
           if (diff < minDiff) {
               minDiff = diff;
           }
           // prevMax = buckets[i][0];
           prevMax = buckets[i][bucketSizes[i]-1];
       }
       return minDiff;
   }
}
  • 执行结果：上述代码中每个桶中的元素个数为1，然后比较相邻非空桶之间数据的差值，记录最小的那个，即为所求。
    在这里插入图片描述