1//建立一个排序用的顺序表结构L
 2#define MAXSIZE 9
 3typedef struct SqList
 4{
 5    int r[MAXSIZE];
 6    int length;
 7}SqList;
 8/*排序的交换函数*/
 9void swap(SqList* L,int i,int j)
10{
11    int temp = L->r[i];
12    L->r[i] = L->r[j];
13    L->r[j] = temp;
14}

 1#define BUCKET_CAP (10)
 2void BucketSort(SqList *L)
 3{
 4    if(L == nullptr || L->length < 2)
 5    {
 6        return;
 7    }
 8
 9    int max = L->r[0], min = L->r[0];
10    //找到最大值最小值
11    for(int i = 0; i < L->length; i++)
12    {
13        if(L->r[i]  > max)
14        {
15            max = L->r[i];
16        }
17        if(L->r[i] < min)
18        {
19            min = L->r[i];
20        }
21    }
22    int bucketCount = (max - min) / BUCKET_CAP + 1;
23    vector<int> buckets[bucketCount];//二维数组，长度为BUCKET_CAP大小的个数为桶的个数
24    // 入桶
25    for (int i = 0; i < L->length; i++) {
26        int idx = (L->r[i] - min) / BUCKET_CAP;			//放入对应的桶
27        buckets[idx].push_back(L->r[i]);
28        if(buckets[idx].size() >= 2)
29        {
30            // 对该桶使用插入排序(因为数据过少，插入排序即可)，维持该桶的有序性
31            for (int j = buckets[idx].size() - 1; j > 0; j--) {
32                if (buckets[idx][j] < buckets[idx][j-1]) {
33                    swap(buckets[idx][j], buckets[idx][j-1]);
34                }
35            }
36        }
37    }
38    // 顺序访问桶，得到有序数组
39    for (int i = 0, k = 0; i < bucketCount; i++) {
40        for (int j = 0; j < int(buckets[i].size()); j++) {
41            L->r[k++] = buckets[i][j];
42        }
43    }
44}

 1//桶的容量，即每个桶所能放置多少个不同数值
 2//bucketCap这里是2
 3public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketCap)
 4{
 5    if(array == null || array.size() < 2)
 6    {
 7        return array;
 8    }
 9    
10    int max = array.get(0), min = array.get(0);
11    //找到最大值最小值
12    for(int i = 0; i < array.size(); i++)
13    {
14        if(array.get(i)  > max)
15        {
16            max = array.get(i);
17        }
18        if(array.get(i) < min)
19        {
20            min = array.get(i);
21        }
22    }
23    //获得桶的数量
24    int bucketCount = (max - min) / bucketCap + 1;
25    //构建桶
26    ArrayList<ArrayList<Interger>> bucketArr = new ArrayList<>(bucketCount);
27    ArrayList<Interger> resultArr = new ArrayList<>();
28    for(int i = 0; i < bucketCount; i++)
29    {
30        bucketArr.add(new ArrayList<Integer>());
31    }
32    //将原始数组中的数据分配到桶中
33    for(int i = 0; i < array.size(); i++)
34    {
35        bucketArr.get((array.get(i) - min) / bucketCap).add(array.get(i));
36    }
37    //看桶中数据的分布
38    for(int i = 0; i < bucketArr.size(); i++)
39    {
40        System.out.println("第" + i + "个桶包含数据");
41        PrintArray.printObject(bucketArr.get(i));
42    }
43    //桶内数据在做相关的排序
44    for(int i = 0; i < bucketCount; i++)
45    {
46        if(1 == bucketCap)
47        {
48            for(int j = 0; j < bucketArr.get(i).size(); j++)
49            {
50                resultArr.add(bucketArr.get(i).get(j));
51            }
52        }else
53        {
54            if(1 == bucketCount)
55            {
56                bucketCap--;
57            }
58            System.out.println("对第" + i + "桶中的数据再次用桶进行排序");
59            ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketCap);
60            for(int j = 0; j < temp.size(); j++)
61            {
62                resultArr.add(temp.get(j));
63            }
64        }
65    }
66    return reslutArr;
67}