vlambda博客
学习文章列表

用Java实现桶排序算法



桶排序核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。每个桶内完成排序后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序序列了。“桶”就是我们存放一组数据的容器。


桶排序过程中存在两个关键环节


①、元素值域的划分,也即元素到桶的映射规则。映射规则需要根据排序集合的元素分布特性进行选择。若规则设计的过于模糊、宽泛,可能导致排序集合中所有元素全部映射到一个桶上,若映射规则设计的过于具体、严苛,则可能导致排序集合中每一个元素值映射到一个桶上。


②、从待排序集合中元素映射到各个桶上的过程,并不存在元素的比较和交换操作,在对各个桶中元素进行排序时,可以选择合适的排序算法,每个桶的排序算法的复杂度和稳定性,决定了最终的算法复杂度和稳定性。


桶排序的核心思想简单易懂,其代码实现也不难。以下代码递归+桶排序完成桶排序算法实现。


package sort;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BucketSort {

    public List<Integer> bucketSort(List<Integer> list, int bucketSize) {
        if (list == null || list.size() <=1 || bucketSize < 1) {
            return list;
        }

        // 确定数组中最大值、最小值
        int maxOfArr = list.get(0);
        int minOfArr = list.get(0);

        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) > maxOfArr) {
                maxOfArr = list.get(i);
            }
            else if (list.get(i) < minOfArr) {
                minOfArr = list.get(i);
            }
        }

        // 确定桶的个数
        int bucketCount = (maxOfArr - minOfArr) / bucketSize + 1;

        // 创建一个数组,用来存储所有桶
        List<List<Integer>> bucketList = new ArrayList<>();
        // 按序将桶添加进去
        for (int i = 0; i < bucketCount; i++) {
            bucketList.add(new ArrayList<Integer>());
        }

        // 将排序数组元素按照顺序放入桶中
        for(int j = 0; j < list.size(); j++) {
            int bucketIndex = (list.get(j) - minOfArr) / bucketSize;
            bucketList.get(bucketIndex).add(list.get(j));
        }

        // 创建一个最终存储结果的列表
        List<Integer> resultList = new ArrayList<>();

        // 对每一个桶中的数据进行排序
        for (int i = 0; i < bucketList.size(); i++) {
            // 依次取出每个桶
            List<Integer> elementList = bucketList.get(i);

            if (elementList.size() > 0) {
                // 如果桶内有元素
                if (bucketCount == 1) {
                    // 当只有一个桶时,缩小桶的大小以获得更多的桶
                        bucketSize--;
                }

                // 递归调用桶排序为每一个桶进行排序
                List<Integer> tempList = bucketSort(elementList, bucketSize);

                for (int j = 0; j < tempList.size(); j++) {
                    resultList.add(tempList.get(j));
                }
            }

        }

        return resultList;
    }


写一段测试代码进行测试,代码和结果如下。


  public void test() {
        // 准备一个数组
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(1);
        list.add(0);
        list.add(6);
        list.add(4);
        list.add(8);
        list.add(9);
        list.add(7);

        System.out.println("排序前:");
        System.out.println(list);

        list = bucketSort(list, 3);

        System.out.println("排序后:");
        System.out.println(list);
    }

// 打印结果
排序前:
[31064897]
排序后:
[01346789]


最后我们做一个总结:


①、桶排序的时间复杂度,取决于对各个桶之间数据进行排序的时间复杂度,如果我们将待排序元素映射到某一个桶的映射规则做的很好,桶划分的越小、各个桶之间的数据越少,排序所用的时间也会越少。当我们对每个桶采用快速排序时如果桶的个数接近数据规模n时,复杂度为O(n),在极端情况下复杂度退化为O(nlogn)。


②、桶排序虽然快,但是它其实是采用了用空间换时间的做法。由于需要开辟新的空间保存元素,并申请空间存放每个桶,所以空间复杂度为O(n+m),m代表桶的个数。


③、桶排序是否稳定取决于每一个桶内排序算法的稳定性,如果使用快速排序就不是一个稳定的排序算法。


今天关于桶排序的分享就到这里了,期待下篇文章见。