欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

桶排序

程序员文章站 2022-05-24 12:48:54
...

桶排序适用于数据量大, 且分布均匀的情况.

 

程序代码:

package rickgong.algorithm.sort;

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

/**
 * Created by rick on 2015/3/8.
 */
public class BucketSortTest {
    public static void main(String[] args) {
        BucketSortTest sortTest = new BucketSortTest();
        int[] array = {84, 32, 87, 24, 67, 52, 85, 13, 53, 48, 21, 95, 98, 21, 45, 12, 75, 72, 54, 62};
        sortTest.printArray(array);
        System.out.println("begin:");

        sortTest.bucketSort(array, 20);
    }

    private void bucketSort(int[] array, int bucketCapacity) {
        //init buckets
        int maxValue = array[0];
        int minValue = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxValue) {
                maxValue = array[i];
            }
            if (array[i] < minValue) {
                minValue = array[i];
            }
        }
        int bucketCount = (int) Math.ceil((maxValue - minValue + 1) * 1.0 / bucketCapacity);
        List<List<Integer>> buckets = new ArrayList<List<Integer>>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(i, new ArrayList<Integer>());
        }

        //fill buckets
        System.out.println("fill each bucket");
        for (int i = 0; i < array.length; i++) {
            int bucketIndex = (array[i] - minValue) / bucketCapacity;
            buckets.get(bucketIndex).add(array[i]);

            printBuckets(buckets);
            System.out.println();
        }

        //sort each bucket
        System.out.println("sort each bucket");
        for (int i = 0; i < buckets.size(); i++) {
            Collections.sort(buckets.get(i));
        }

        printBuckets(buckets);
    }

    private void printBuckets(List<List<Integer>> buckets) {
        for (int i = 0; i < buckets.size(); i++) {
            System.out.print("{");
            List<Integer> bkt = buckets.get(i);
            for (int j = 0; j < bkt.size(); j++) {
                System.out.print(bkt.get(j) + "\t");
            }
            System.out.print("}");
        }
    }

    private void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
    }

    private void assertSorted(int[] array) {
        boolean sorted = true;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                sorted = false;
                break;
            }
        }
        if (!sorted) {
            throw new RuntimeException("Not sorted");
        }
    }
}

 

输出结果:

84 32 87 24 67 52 85 13 53 48 21 95 98 21 45 12 75 72 54 62
begin:
fill each bucket
{}{}{}{84 }{}
{}{32 }{}{84 }{}
{}{32 }{}{84 87 }{}
{24 }{32 }{}{84 87 }{}
{24 }{32 }{67 }{84 87 }{}
{24 }{32 }{67 52 }{84 87 }{}
{24 }{32 }{67 52 }{84 87 85 }{}
{24 13 }{32 }{67 52 }{84 87 85 }{}
{24 13 }{32 }{67 52 53 }{84 87 85 }{}
{24 13 }{32 48 }{67 52 53 }{84 87 85 }{}
{24 13 21 }{32 48 }{67 52 53 }{84 87 85 }{}
{24 13 21 }{32 48 }{67 52 53 }{84 87 85 }{95 }
{24 13 21 }{32 48 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 }{32 48 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 }{32 48 45 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 }{84 87 85 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 }{84 87 85 75 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 }{84 87 85 75 72 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 54 }{84 87 85 75 72 }{95 98 }
{24 13 21 21 12 }{32 48 45 }{67 52 53 54 62 }{84 87 85 75 72 }{95 98 }
sort each bucket
{12 13 21 21 24 }{32 45 48 }{52 53 54 62 67 }{72 75 84 85 87 }{95 98 }

 

相关标签: 算法 桶排序