算法导论 基数排序

基数排序O(d(n+k)) ---》 O(n);
用下面代码解释字母含义
d;最大元素的长度,决定了桶的数量
k;每一轮计数排序都需要辅助运算,k较大

逻辑比较简单,每一个桶用一次计数排序排序,分别排序个位,排序十位,排序百位,以此类推,最后有序。
源码走起
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#define N 2000
#define K 1000
void Printf(int* p, int n);//打印
int find_max(int* p, int n);//找到最大值
int place(int n);//最大值有多少位
void happen_rand(int* p, int n);//生成随机数
int car_num(int* p, int n);//基数排序
int get_value(int n,int k);//得到第k位的值
int main()
{
    
    int array[N] = { 0 };
    happen_rand(array,N);
    car_num(array, N);
    Printf(array, N);
    return 0;
}

void happen_rand(int* p, int n)
{
    srand();
    for (int i = 0; i < N; i++) {
        p[i] = rand() % K;

    }
}

int find_max(int* p, int n)
{
    int tmp = p[0];
    for (int i = 1; i < n; i++) {
        tmp < p[i] ? tmp = p[i] : tmp;
    }
    return tmp;
}

int place(int n) {

    int tmp = 0;
    while (n > 0) {
        n /= 10;
        tmp++;
    }
    return tmp;
}

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

int get_value(int n,int k) {
    while (k-->1) {
        n /= 10;
    }
    n %= 10;
    return n;
}

int car_num(int* p, int n) {
    int max = find_max(p, n);
    int len = place(max);
    int answer[N] = { 0 };
    for (int i = 0; i < len; i++) {
        int tmp[10] = { 0 };
        for (int j = 0; j < n; j++) {
            tmp[get_value(p[j],i+1)]++;
        }//计数排序内容,详见前期博客
        for (int i = 1; i < 10; i++) {
            tmp[i] += tmp[i - 1];
        }//计数排序内容,详见前期博客
        for (int l = 0; l < n; l++) {
            answer[tmp[get_value(p[l], i + 1)] - 1] = p[l];
            tmp[get_value(p[l], i + 1)]--;
        }//计数排序内容,详见前期博客
        for (int i = 0; i < n; i++) {
            p[i] = answer[i];
        }



    }


    return 0;
}

全部评论

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务