桶排序的算法

桶排序算法要求，数据的长度必须完全一样，程序过程要产生长度相同的数据，使用下面的方法：Data=rand()/10000+10000上面提到的，每次下一次的扫描顺序是按照上次扫描的结果来的，所以设计上提供相同的两个桶数据结构。前一个保存每一次扫描的结果供下次调用，另外一个临时拷贝前一次扫描的结果提供给前一个调用。

数据结构设计：链表可以采用很多种方式实现，通常的方法是动态申请内存建立结点，但是针对这个算法，桶里面的链表结果每次扫描后都不同，就有很多链表的分离和重建。如果使用动态分配内存，则由于指针的使用，安全性低。所以，笔者设计时使用了数组来模拟链表（当然牺牲了部分的空间，但是 *** 作却是简单了很多，稳定性也大大提高了）。共十个桶，所以建立一个二维数组，行向量的下标0—9代表了10个桶，每个行形成的一维数组则是桶的空间。

平均情况下桶排序以线性时间运行。像基数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具 体来说，基数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间[0，1)上。 桶排序的思想就是把区间[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0，1)上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。

在桶排序算法的代码中，假设输入是含n个元素的数组A，且每个元素满足0≤ A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶，并假设可以用某种机制来维护这些表。

桶排序的算法如下(伪代码表示)，其中floor(x)是地板函数，表示不超过x的最大整数。

procedure Bin_Sort(var A:List)begin

n:=length(A)

for i:=1 to n do

将A[i]插到表B[floor(n*A[i])]中

for i:=0 to n-1 do

用插入排序对表B[i]进行排序

将表B[0],B[1],...,B[n-1]按顺序合并

end

右图演示了桶排序作用于有10个数的输入数组上的 *** 作过程。(a)输入数组A[1..10]。(b)在该算法的第5行后的有序表(桶)数组B[0..9]。桶i中存放了区间[i/10，(i+1)/10]上的值。排序输出由表B[O]、B[1]、...、B[9]的按序并置构成。

要说明这个算法能正确地工作，看两个元素A[i]和A[j]。如果它们落在同一个桶中，则它们在输出序列中有着正确的相对次序，因为它们所在的桶是采用插入排序的。现假设它们落到不同的桶中，设分别为B[i']和B[j']。不失一般性，假设i' i'=floor(n*A[i])≥floor(n*A[j])=j' 得矛盾 (因为i' 来分析算法的运行时间。除第5行外，所有各行在最坏情况的时间都是O(n)。第5行中检查所有桶的时间是O(n)。分析中唯一有趣的部分就在于第5行中插人排序所花的时间。

为分析插人排序的时间代价，设ni为表示桶B[i]中元素个数的随机变量。因为插入排序以二次时间运行，故为排序桶B[i]中元素的期望时间为E[O(ni2)]=O(E[ni2])，对各个桶中的所有元素排序的总期望时间为：O(n)。(1) 为了求这个和式，要确定每个随机变量ni的分布。我们共有n个元素，n个桶。某个元素落到桶B[i]的概率为l/n，因为每个桶对应于区间[0，1)的l/n。这种情况与投球的例子很类似：有n个球 (元素)和n个盒子 (桶)，每次投球都是独立的，且以概率p=1/n落到任一桶中。这样，ni=k的概率就服从二项分布B(kn,p)，其期望值为E[ni]=np=1，方差V[ni]=np(1-p)=1-1/n。对任意随机变量X，有右图所示表达式。

(2)将这个界用到(1)式上，得出桶排序中的插人排序的期望运行时间为O(n)。因而，整个桶排序的期望运行时间就是线性的。

#define Max_len 10      //数组元素个数

// 打印结果

void Show(int  arr[], int n)

{

    int i

    for ( i=0 i<n i++ )

        printf("%d  ", arr[i])

    printf("\n")

}

//获得未排序数组中最大的一个元素值

int GetMaxVal(int* arr, int len)

{

    int maxVal = arr[0] //假设最大为arr[0]

    for(int i = 1 i < len i++)  //遍历比较，找到大的就赋值给maxVal

    {

        if(arr[i] > maxVal)

            maxVal = arr[i]

    }

    return maxVal  //返回最大值

}

//桶排序   参数：数组及其长度

void BucketSort(int* arr , int len)

{

    int tmpArrLen = GetMaxVal(arr , len) + 1

    int tmpArr[tmpArrLen]  //获得空桶大小

    int i, j

    for( i = 0 i < tmpArrLen i++)  //空桶初始化

        tmpArr[i] = 0

    for(i = 0 i < len i++)   //寻访序列，并且把项目一个一个放到对应的桶子去。

        tmpArr[ arr[i] ]++

    for(i = 0, j = 0 i < tmpArrLen i ++)

    {

        while( tmpArr[ i ] != 0) //对每个不是空的桶子进行排序。

        {

            arr[j ] = i  //从不是空的桶子里把项目再放回原来的序列中。

            j++

            tmpArr[i]--

        }

    }

}

int main()

{   //测试数据

    int arr_test[Max_len] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 }

    //排序前数组序列

    Show( arr_test, Max_len )

    //排序

    BucketSort( arr_test,  Max_len)

    //排序后数组序列

    Show( arr_test, Max_len )

    return 0

}