《算法导论》8-4节之桶排序算法（线性时间排序）

桶排序的思想就是把区间[0, 1)划分成n个相同大小的子区间，或者叫做桶，然后将n个输入数分布到各个桶中，然后对桶中的数进行排序，最后按照次序依次输出各个桶中已经排好序的数。

计数排序假设输入数是由一个小范围内的整数构成；
而桶排序假设输入是由一个随即过程产生，该过程将输入元素均匀且独立的分布在区间[0, 1)上。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

//

#define MAX 100
float a[10] = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};

typedef struct node{
        float val;
        struct node *next;
}node;
typedef struct headnode{
        int num;
        node *next;
}headnode;
headnode b[10];


int compare(const void *a, const void *b);
int main(int argc, char **argv)
{
        int i = 0, j = 0, pos = 0, k = 0;
        float tempval, sort[MAX];
        node *newnode = NULL, *tempnode = NULL;

//Init b[10]

        for(i = 0; i < 10; i++){
                b[i].num = i;
                b[i].next = NULL;
        }

//Insert

        for(i = 0; i < 10; i++){
                newnode = (node *)malloc(sizeof(node));
                newnode->val = a[i];

                pos = (int)(floorf(10 * newnode->val));
                newnode->next = b[pos].next;
                b[pos].next = newnode;
        }

        for(i = 0; i < 10; i++){
                if(b[i].next != NULL){
                        memset((void *)sort, MAX, sizeof(float));
                        tempnode = b[i].next;
                        j = 0;
                        while(tempnode != NULL){
                                        sort[j++] = tempnode->val;
                                        tempnode = tempnode->next;
                        }

                        qsort((void *)sort, j, sizeof(float), compare);
                        tempnode = b[i].next;
                        for(k = 0; k < j; k++){
                                tempnode->val = sort[k];
                                tempnode = tempnode->next;
                        }
                }
        }

//Output the result

        for(i = 0; i < 10; i++){
                if(b[i].next != NULL){
                        tempnode = b[i].next;
                        while(tempnode != NULL){
                                printf("%.2f ", tempnode->val);
                                tempnode = tempnode->next;
                        }
                }
        }
        printf("\n");

        for(i = 0; i < 10; i++){
                if(b[i].next != NULL){
                        free(b[i].next);
                }
        }

        return 0;
}

int compare(const void *a, const void *b)
{
        return ((*((float *)a)) * 100 - (*((float *)b) * 100));
}


执行：
[xxxx@localhost suanfa]$ ./a.out
0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94