桶排序

桶排序（Bucket Sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

算法描述

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。

实例

代码实现

import java.util.*;
public class BucketTest {
    public static void main(String[] args) {
        float[] a = {0.12f, 2.2f, 8.8f, 7.6f, 7.2f, 6.3f, 9.0f, 1.6f, 5.6f, 2.4f};
        System.out.println("初始值:");
        printArray(a);
        bucketSort(a);
        System.out.println("\n排序后:");
        printArray(a);
    }
    
    public static void bucketSort(float[] arr) {
        // 新建一个桶的集合
        ArrayList<LinkedList<Float>> buckets = new ArrayList<LinkedList<Float>>();
        for (int i = 0; i < 10; i++) {
            // 新建一个桶，并将其添加到桶的集合中去。
            // 由于桶内元素会频繁的插入，所以选择 LinkedList 作为桶的数据结构
            buckets.add(new LinkedList<Float>());
        }
        // 将输入数据全部放入桶中并完成排序
        for (float data : arr) {
            int index = getBucketIndex(data);
            insertSort(buckets.get(index), data);
        }
        // 将桶中元素全部取出来并放入 arr 中输出
        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); // 否则把数据插入到链表末端
        }
    }
    
    private static void printArray(float[] a) {
        for (int i = 0;i < a.length;i++) {
            System.out.print(a[i] + " ");
        } 
        System.out.println();
    }
    }
    
    /**
    * 创建堆算法
    */
    public static void sink(int[] a,int lastIndex) {
        for(int i = (lastIndex-1)/2;i >= 0;i--) {
            int k = i;
            while(2 * k + 1 <= lastIndex) {
                int bigIndex = 2*k+1;
                if(bigIndex < lastIndex) {
                    if(a[bigIndex] < a[bigIndex + 1]) {
                        bigIndex++;
                    }
                }
                
                if(a[k] < a[bigIndex]) {
                    exch(a,k,bigIndex);
                    k = bigIndex;
                }else {
                    break;
                }
            }
        }
    }
    
    /**
    * 交换两元素
    */
    public static void exch(int[] a,int i,int j) {
        if(i == j) {
            return;
        }
        a[i] = a[i] + a[j];
        a[j] = a[i] - a[j];
        a[i] = a[i] - a[j];
        
    }
}