桶排序

     桶排序的基本思想就是待排序的数据分别放入不同的桶中，这些桶之间其实是有序的。然后在这些桶中将分在里面的数据进行排序。最终就完成了整个序列的排序。

     假设将一个均匀分布在区间[0,200)的一些待排序的序列，分成20个桶中。每个桶的大小都是10。分别存数据[0, 9), [10, 19), [20, 29) …. [190, 199)，将待排序数组中的数据分别存进这些桶中，然后分别对桶中的元素进行排序，这样就完成了排序。      比如有数据{32, 43, 1, 65, 43, 57, 83, 93, 73, 22, 28, 53}，将这些数据在区间[0, 100)中，将这些数据分进十个桶中，然后在这些桶中对其中的数据进行排序。如下图所示：      其实桶排序最终构建的结构是一个散列表。

typedef int datatype;//numberLimits是数据区间的最大值，如果传入200,其区间就是[0, 200)int BucketSort(datatype *array, int size, int numberLimits){    int i, j;    //temp是一个指针数组    Node **temp;    Node *p, *s;    if(array == NULL) {        return -1;    }    //给指针数组temp分配空间    temp = (Node **)calloc(numberLimits / 10 + 1, sizeof(Node *));    if(temp == NULL) {        return -1;    }    for(i = 0; i < size; i++) {        p = temp[array[i] / 10];    //创建一个节点        s = (Node *)malloc(sizeof(Node));        if(s == NULL) {            return -1;        }        s->data = array[i];        s->next = NULL;        if(p == NULL)//如果最开始这个桶为空，则直接将这个结点存入        {            temp[array[i] / 10] = s;        } else {
    //如果桶不为空            //如果第一个结点的数据大于需要插入的数据            if(p->data > s->data) {                s->next = p;                temp[array[i] / 10] = s;            } else {            //在桶中查找需要查找的位置                while(p->next != NULL && p->next->data < s->data)                    p = p->next;                s->next = p->next;                p->next = s;            }        }       }    //根据这些桶重新给数组赋值，最终的结果就是一个有序的序列    for(i = 0, j = 0; i < numberLimits / 10 + 1; i++) {        p = temp[i];        while(p) {            array[j++] = p->data;            p = p->next;        }    }    return 0;}