排序算法之桶排序_桶排序最坏情况

桶排序算法思想

桶排序的思想是把[0，1)划分为n个大小相同的子区间，每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0，1)上的，所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同，所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序，然后依次将各非空桶中的记录连接(收集)起来即可。

最坏情况时间复杂度：当分布不均匀时，全部元素都分到一个桶中，则O(n^2);最好情况分到不同的桶时间复杂度O(n)；桶排序的平均时间复杂度是线性的，即 O(n)。

//桶排序
BUCKET_SORT(A)
    n = length[A]
    create buckets B[n]
    for i=1 to n
        insert A[i] to B[A[i]]
    for i=0 to n-1
        sort B[i] with INSERTION_SORT
    concatenate B[]
1
2
3
4
5
6
7
8
9

这里是一个简单的实现，没有用链表，如果待排数组很大很大，这个实现就不合适了。此外，打断点来看看该算法的运作，会更容易理解

public static void bucketSort(int[] array)
{
    int bucketSize = getMaxVal(array,array.length) + 1;
    int i,j;

    //创建桶,JVM初始化数组
    int[] bucket = new int[bucketSize];

    //遍历数组，并且把数字一个一个放到对应的桶去
    for (i = 0; i < array.length; i++)
    {
        bucket[array[i]]++;
    }
    //遍历桶
    for (i = 0, j = 0; i < bucketSize; i++) 
    {
        //对每个不是空的桶子进行排序
        while (bucket[i] != 0)
        {
            //bucket的下标恰好是待排数组的值
            array[j] = i;
            j++;
            //桶里没东西了，置为0
            bucket[i]--;
        }
    }
}


public static void getMaxVal(int[] array, int length)
{
   int maxVal = array[0];
   for (int i = 1; i < length; i++)
   {
       if (array[i] > maxVal)
       {
           maxVal = array[i];
       }
   }
   return maxVal;
}
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