算法导论 桶排序

源码走起

----------------------------------------------------------------------------------------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 20000
#define K 100
void happen_rand(float* p, int n);//生成随机数
void bucket(float* p, int n);//桶排序
int get_value(float n);//得到小数第一位的值，作为桶排序的区间
void Printf(float* p, int n);;//打印

int main()
{
    float array[N] = { 0 };
    happen_rand(array, N);
    bucket(array, N);
    Printf(array, N);

    return 0;
}
void happen_rand(float* p, int n)
{
    
    for (int i = 0; i < N; i++) {
        p[i] = rand() % K;
        p[i] /= 100.0;
        
    }
}

int get_value(float n) {
    n = n * 10;
    int tmp = (int)n;
    tmp = tmp % 10;
    return tmp;
}


void bucket(float* p, int n) {
    
    float buck[10][N] = { 0 };
    int sum[10] = { 0 };
    for (int i = 0; i < n; i++) {//元素放到10个桶里面
        buck[get_value(p[i])][sum[get_value(p[i])]] = p[i];
         sum[get_value(p[i])]++;//记录每个桶有多少个元素
    }
    for (int i = 0; i < 10; i++) {//每个桶进行计数排序，计数排序详见前期博客
        float tmp[N] = { 0 };
        int count[10] = { 0 };
        for (int j = 0; j < sum[i];j++) {
            count[(int)(buck[i][j]*100)%10]++; 
        }
        for (int j = 1; j < 10; j++) {
            count[j] += count[j - 1];
        }
        for (int j = 0; j < sum[i];j++) {
            tmp[count[(int)(buck[i][j] * 100) % 10] - 1] = buck[i][j];
            count[(int)(buck[i][j] * 100) % 10]--;//这个地方漏写，让我找了一个小时，心疼一整天
        
        for (int j = 0; j < sum[i]; j++) {
            buck[i][j] = tmp[j];
        }

    }
    int tmpcoun = 0;
    for (int i = 0; i < 10; i++) {//十个桶的数据倒出来
        for (int j = 0; j < sum[i]; j++) {
            p[tmpcoun] = buck[i][j];
            tmpcoun++;
        }
    }

}

void Printf(float* p, int n) {
    for (int i = 0; i < n; i++) {
        printf("%.2lf\n", p[i]);
    }
}