LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

算法一:桶排序

Clicks: 10627 Date: 2014-10-27 22:28:08 Power By 李轩Lane

    

桶排序, 是最快最简单的排序。有多宽维度,就要申请多大的数组。比如100分的试卷,就要申请101个数组(试卷是0-100分),有人考了100分,就把array[100]加1,有人考了90,就把array[90]加1,有人考了70,就把array[70]+1,又有人考了90,就把array[90]加1,那么从高到底打印,如果是某个分数是0个人,就不打印,如果某个分数是1个人,就打印一次,如果某个分数是2个人,就打印两次,上面的例子就是100,90,90,90,70。

桶排序快是毋庸置疑的,但是,浪费了空间。比如打游戏,新手村里的小鸡攻击力是1,而最后一个副本的大BOSS的攻击力是999999999,那么就要对这个游戏的所有玩家和怪物的攻击力排序,就要申请一个1000000000长度的数组,就是array[1000000000]。假如每个字段的值都是1,1是整形,需要是4-8个字节(到底是4还是8取决于机器),那么这个数组就是1000000000/8/1024/1024=119MB。嗯哼?一个数组就要119M,你就是13年淘宝双11的160G内存的机器也拖不起吧。

桶排序的时间复杂度是O(M+N),是最快的排序,它也是最简单的排序。


C语言代码:

#include <stdio.h>

int main(){

    int i, j, num, score, rank[100];

    for(i=0; i<101; i++){

        rank[i] = 0;

    }

    //需要录入多少个数据

    printf("How many?\n");

    scanf("%d", &num);

    for(i=0; i<num; i++){

        printf("Enter Score:\n");

        scanf("%d", &score);

        //我们的试卷是0-100分的哦

        if(score<0 || score > 100){

            printf("Error");

            return 1;

        }

        //进桶

        rank[score]++;

        score = 0;

    }

    printf("Rank:\n");

    //打印

    for(i=0; i<101; i++){

        for(j=0; j<rank[i]; j++){

            printf("%d,", i);

        }

    }

}

Reply: ewodimauu On 2020-02-22 05:49:30

http://mewkid.net/who-is-xandra/ - Amoxicillin Without Prescription <a href="http://mewkid.net/who-is-xandra/">Amoxicillin</a> dla.vses.lanecn.com.wue.mt http://mewkid.net/who-is-xandra/

回复

Reply: epecyozag On 2020-02-22 06:29:10

http://mewkid.net/who-is-xandra/ - Amoxicillin No Prescription <a href="http://mewkid.net/who-is-xandra/">Amoxicillin No Prescription</a> gqj.pebe.lanecn.com.tsc.vj http://mewkid.net/who-is-xandra/

回复

Reply: Leslext On 2020-03-08 21:34:42

Canadian Family Pharmacy Online Canada http://apcialisle.com/# - Buy Cialis Vendo Cialis Italia <a href=http://apcialisle.com/#>Buy Cialis</a> Priligy Etats

回复

Reply: Leslext On 2020-03-17 04:52:57

Propecia Fue Bueno http://apcialisle.com/# - Buy Cialis Doryx Discount Ups Mastercard <a href=http://apcialisle.com/#>buy generic cialis</a> Genericos De Propecia 1 Mg

回复

Reply: Franksow On 2020-04-17 07:49:16

https://itopdeals.eu https://mootools.net/forge/profile/Adriah+giubloodatto1979 https://topsexdatingwebsites.arganique.eu https://freeaccesssexdating.jesus2go.eu https://freensadatingsites.arganique.eu https://topsexdatingsite.sikerkulcs.eu https://datingsimsexgames.go4itmagazine.eu

回复

Reply: Ketavawl On 2020-04-30 15:46:32

Il Cialis Generico E Sicuro? <a href=https://viacialisns.com/#>Cialis</a> Viagra Per Ansia <a href=https://viacialisns.com/#>cialis canada</a> Keflex Upper Respiratory Infection

回复

Reply: Mervin On 2020-05-30 02:24:20

After I initially commented I seem to have clicked the -Notify me when new comments are added- checkbox and from now on every time a comment is added I receive 4 emails with the same comment. There has to be a way you are able to remove me from that service? Cheers!

回复

Reply: Denis On 2020-09-25 13:57:55

viagra coupon https://genviagara.com - viagra online no prescription generic viagra soft non prescription viagra generic viagra price canadian pharmacies

回复

Reply: Emmanuel On 2020-10-06 07:25:36

viagra for men price https://viagarat.com - online viagra female viagra pills viagra online prescription free viagra 100 mg price viagra price

回复

Add Comment
©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号