Java基础系列--桶排序

时间:2021-09-24 09:27:46

原创作品,可以转载,但是请标注出处地址:http://www.cnblogs.com/V1haoge/p/9045967.html

1、算法简介

  桶排序可以算是最简单快速的排序算法了,只是限定条件要多一点,需要事先知晓待排序列的极限值或范围来准备足够的桶。

2、算法原理

  桶排序的原理就是准备足够数量的有序桶(一般用数组实现),用标记待排序列的每个元素,用元素值对应桶下标,桶里的值代表的是元素对应的值出现的次数,有一次就在原值上加1(初始值为0)。当将所有的待排序列中的元素遍历一遍后,将其全部标记到桶中,这时候其实就已经排好序了。如果我们需要正序排序,则对桶进行正序遍历,排除值为0 的桶,按顺序和通中值的个数输出桶的下标值,即为正序列,倒序反之。

3、算法实现

 public class BusketSort {

   public static void sort(int[] ints, Boolean isAsc) {
     int[] basket = new int[101]; //定义足够大的数组桶
     for (int i : ints) {
       basket[i]++; //对应元素的桶下标自增
     }
     if (isAsc) {
       for (int i = 0; i < basket.length - 1; i++) {
         if (basket[i] > 0) {
           for (int j = 1; j <= basket[i]; j++) {
             System.out.print(i + " "); //循环输出桶元素不为0的下标值
           }
         }
       }
     } else {
       for (int i = basket.length - 1; i > 0; i--) {
         if (basket[i] > 0) {
           for (int j = 1; j <= basket[i]; j++) {
             System.out.print(i + " "); //循环输出桶元素不为0的下标值
           }
         }
       }
     }

   }

   public static void main(String[] args) {
     int[] ints = {2, 6, 4, 9, 12, 98, 5, 32, 90, 33, 24, 65, 37, 12, 4};
     sort(ints, false);
   }
 }

4、算法解析

  首先我们需要准备一个桶数组,桶数组的大小为已知的待排序列的范围,比如我们要对学生的单科成绩(满分100)进行排序,那么我们就要准备101个桶(即定义一个长度为101的数组)。

  然后遍历待排序列,将与待排元素值一致的桶下标对应的桶的值加1(初始值为0),遍历结束,其实排序也就完成了。

  最后,我们需要正序排序则,正序遍历桶输出桶下标,倒序则倒序遍历桶输出桶下标(需要注意的就是下标输出的次数为下标对应的桶值)。

4.1 时间复杂度

  桶排序的时间复杂度是O(m+n),其中m为待排序元素个数,n为桶数。

4.2 空间复杂度

  桶排序的空间复杂度极大,与待排序的最大元素相关。

5、总结

  从代码实现中我们也可以看出,桶排序是及其简单的,唯一的缺陷就是桶的存在及其占用空间,如果我们要排序的数列只有很少的个数,但是元素之间相差极大的话,那么我们就需要准备一个极大的桶,及其浪费空间资源。一般情况下我们会在一个桶中存放一个范围之内的元素,桶中的元素我们可以采用其他的排序算法实现排序。这样可以极大的降低空间消耗。

  桶排序一般适用于如下场景:

     数据分布相对较为均匀或者数据范围不大的情况下

    特殊场景,比如需要统计元素的个数的情况,或者希望通过哈希映射快速获取某些值的情况