概述
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)
算法描述
- 设置一个定量的数组当作空桶
- 遍历输入数据,并且把数据一个一个放到对应的桶里去
- 对每个不是空的桶进行排序
- 从不是空的桶里把排好序的数据拼接起来
图片演示
算法实现
Java代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
| package com.ledao;
import java.util.*;
public class Test {
public static void main(String[] args) { float[] arr = new float[]{0.12f, 2.2f, 8.8f, 7.6f, 7.2f, 6.3f, 9.0f, 1.6f, 5.6f, 2.4f}; bucketSort(arr); printArray(arr); }
public static void bucketSort(float[] arr) { ArrayList<LinkedList<Float>> buckets = new ArrayList<LinkedList<Float>>(); for (int i = 0; i < 10; i++) { buckets.add(new LinkedList<Float>()); } for (float data : arr) { int index = getBucketIndex(data); insertSort(buckets.get(index), data); } int index = 0; for (LinkedList<Float> bucket : buckets) { for (Float data : bucket) { arr[index++] = data; } } }
public static int getBucketIndex(float data) { return (int) data; }
public static void insertSort(List<Float> bucket, float data) { ListIterator<Float> it = bucket.listIterator(); boolean insertFlag = true; while (it.hasNext()) { if (data <= it.next()) { it.previous(); it.add(data); insertFlag = false; break; } } if (insertFlag) { bucket.add(data); } }
public static void printArray(float[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + ", "); } System.out.println(); } }
|
运行结果
算法分析
桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大
PS.
搬运地址: 十大经典排序算法(动图演示) - 一像素 - 博客园 (cnblogs.com)