对于程序员而言，这种小电脑一般场合足够用了，当然只要不玩大游戏。装个无线网卡，兼做路由器连接WIFI设备，室内连路由器都不需要了。8GB内存装64位Win7系统，其实再装几个虚拟机也行，播放音乐用蓝牙连音箱足矣。处理器虽然是I5，但是双核四线程的，跟I3差不多，只不过最大睿频可以到2.6GHz，单核心最大睿频2.8GHz，平时则是800MHz待机状态。无论跟下图21.5寸显示器比，还是跟联想的键盘比，机箱实在是太小了，甚至比联想的激光小鼠标都大不了太多。为了尽可能节约空间，天线直接贴在机箱内壁就行，反正机箱不是金属的，挡不住电磁波。下图无线信号看上去似乎不是很强啊，这些信号源是哪层楼的不清楚，可能都不在本栋楼。天线是笔记本里用的那种贴片天线型号，两根4DB的增益天线。上面那个太小了，只有12厘米X12厘米X6厘米，下面这个稍大一些，大约20厘米X20厘米X6.5厘米。这货用的Intel I3 3220T处理器，CPU TDP是35W的，CPU平时待机1.6GHz，高负荷下2.8GHz，I3不能睿频率。也用DC-19V笔记本砖块电源供电。跟23寸的显示器对比如下这样，显示器能直接放上面，其实也占不了多大空间，硬盘可以装2.5寸的两块。或者一块2.5寸，一块3.5寸也行，但两块3.5寸装不下。这两个天线格外显眼，机箱是金属的，屏蔽电磁波，所以无线网卡天线必须引出来，天线这么大，两根8D ...继续阅读 (16)

原来发过搜索第一位的帖子，这次算再补充一下吧。以下取自网络，作者不详。Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/1#ifdef __GNUC__23#if(defined _WIN64 || defined __x86_64__)45/**6* ../bit_scan_forward7* @return index (0..63) of least significant one bit8*/9unsigned bit_scan_forward(unsignedlonglongx)10{11asm("bsfq %0, %0":"=r"(x) :"0"(x));12returnunsigned(x);13}1415/**16* bit_scan_reverse17* @return index (0..63) of most significant one bit18*/19unsigned bit_scan_reverse(unsignedlonglongx)20{21asm("bsrq %0, %0":"=r"(x) :"0"(x));22returnunsigned(x);23}2425#elif(defined _WIN32) | ...继续阅读 (28)

摘要: 写过单数组和双数组哈希表的设计，再来个拉链哈希凑数。拉链哈希是最常用的一种哈希表，也是多数C++标准库实现unordered_xxx时最常用的数据结构。由于每个节点都是动态创建的，因此除了分配内存的时间开销，每块内存还有metadata，对于存储小对象来说，很不划算，但是比较适合存储大的数据结构，例如字符窜。存储整数的示意图如下。实现哈希表最简单的做法就是用std::vector和std::for...阅读全文Chipset2014-06-15 17:26发表评论 ...继续阅读 (29)

How many bytes for a specified file?Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/12#if(defined __unix__) || (defined _WIN64) || (defined _WIN32)3#includetypes.h>4#include5#else6#include7#endif89#if(defined __unix__)1011unsignedlonglongfile_length(constchar*file)12{13structstat64 st;14interr=stat64(file,&st;);15if(0!=err)16return0;17returnstatic_cast(st.st_size);18}1920#elif(defined _WIN32) || (defined _WIN64)2122//Microsoft has some extensions to support Unix!23unsignedlonglongfile_length(constchar*file)24{25struct__stat64 st;26interr=_stat64(f ...继续阅读 (17)

摘要: [This is an opportunity to practice my English. Please correct me should you find any mistake.]Thermal grease (also called thermal gel, thermal compound, thermal paste, heat paste, heat sink paste or ...阅读全文Chipset2014-01-05 18:07发表评论 ...继续阅读 (20)

摘要: 想找段代码统计注释行和代码行，在网上搜了半天也没有找到，干脆自己写一个算啦。。。懒得罗嗦，直接看代码就行了，下面的代码里如果不用map，用vector更好。Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 //&nb...;阅读全文Chipset2013-08-24 23:46发表评论 ...继续阅读 (37)

摘要: 比较不同版本代码差异的工具多如牛毛，但基本原理都一样，都需要比较两个不同版本代码文件的差异和相同之处。最终都需要逐行比较内容(有时可能需要忽略空格，Tab字符等)，这个算法的基本原理如下：(假设a, b, c...顺序代表两个源代码文件的不同代码行) 老版本文件 : a b ...阅读全文Chipset2013-05-25 18:57发表评论 ...继续阅读 (15)

摘要: 以静态表为例，原理如下图，也就是多个单链表存储在同一个数组中。勉强算开地址哈希表吧，但跟一般开地址哈希表原理不太一样。存储在同一个数组的目的是节省一个表头指针，有表头指针的哈希表见本主页"双数组哈希unordered_xxx"相对于传统的拉链哈希表，这个哈希表的原理不太好理解(传统的好理解，但耗费内存多且速度慢～～)看上图。使用默认值覆盖的原因是我们原本用它计算陆地坐标，(0,0,0)这个点在海里...阅读全文Chipset2012-09-09 22:53发表评论 ...继续阅读 (49)

摘要: 简单的类层次结构以静态表unorered_set为例，工作原理见下图简单的效率测试 Sample是本处讲述的双数组unordered_xxx，standard是编译器的unordered_xxx，boost1.50表示它的unordered_xxx测试环境： Win7 x64 Ultimate (Kernel 6.1.7601), g++4.6.3 64bit (-O3), Intel Xeo...阅读全文Chipset2012-08-26 16:49发表评论 ...继续阅读 (20)

摘要: 从数学理论上来讲，没有可行的方案用于设计“完美”的哈希函数。现实中，哈希的设计显然不是技术问题，而是艺术问题。但是请记住：任何一种哈希总有它的优缺点。先看代码：Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> &nbs...;阅读全文Chipset2012-08-08 19:35发表评论 ...继续阅读 (27)

一直追求的目标是写出高效低内存消耗的程序，时间久了觉得换个方向了，呵呵。就拿排序试试吧。bogo sort又称stupid sort或slow sort，我觉得应该是最慢的排序算法了吧，至少理论上比蜗牛排序(本主页有介绍)慢。该排序算法的思想是对于一个给定的序列，随机的生成各种可能的序列，直到遇到某个序列有序为止。时间复杂度最好情况下是O(n)，最坏情况下是无穷大，一般情况是O(n*n!)，可见相当的恐怖。看代码就明白了。Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/1//bogo_sort.hpp2#ifndef BOGO_SORT_HPP_3#defineBOGO_SORT_HPP_45template6boolis_sorted(ForwardIterator first, ForwardIterator last, Compare cmp)7{8if(first==last)9returntrue;10ForwardIterator next=first;11for(++next; next!=last; first=next,++next)12if(cmp(*next,*first))13returnfalse;14returnt ...继续阅读 (20)

1972年农历11月22日，我出生在灌阳县文市镇集全村江边屯，我的出生给全家带来了欢愉和希望，所以父亲给我起名“幸福”，期盼我一生安安康康、衣食无忧。而我为了追求到自己的幸福，也是注定要付出艰辛和努力的。]选择中师，说不清的无奈1988年的那个秋天，天空显得有点阴霾，但又没有刮风下雨的半点迹象，气候正如我的心情一样，说不出是高兴还是淡定，反正一切是说不清道不明的感觉。体检完身体回来，我坐在村头的溪流边，像一位小老头一样思考着自己的未来。作为农家的小孩，我能考上兴安师范已经算是非常的幸运了。母亲因为有远房的亲戚不上中师最后考上大学的先例极力赞成我上高中，然而保守的父亲在保守的乡亲中作过一番调查后，只是送了我一句“你想上高中看谁供你”的话。精打细算的父亲再次跟我说：“你是家里的老大，况且外面的大学生也有许多，上了又能怎么样？不如早读早出来。不过你要读高中可以，给你钱，但你必须写保证书，一定要考上大学。”母亲说写什么写，我也觉得，父亲并不是真正的苛刻，他只不过是想“逼”我去读师范罢了。于是，就在那个有些说不清道不明的深秋，我坐着蹦蹦乱跳的拖拉机在颠簸中离开了我的村落，将听惯了的鸡鸣狗叫抛在脑后，宣告16岁的我将独自踏上一段艰辛的路。送别的时候，母亲站在村边的老树下哭了，父亲也一改往日的威严，抽 ...继续阅读 (22)

摘要: 编程语言烽火台 v11.1 2013年1月 Chipset于2013年02月10日译, For English version, please visit: http://www.lextrait.com/vincent/implementations.html 该表包含了主要软件产品或应用，以及实现所用的编程语言详细信息。有关信息很难找到，个别小错误可能会掠过作者的眼帘，欢迎给出修...阅读全文Chipset2011-12-21 20:34发表评论 ...继续阅读 (18)

去年前DIY了一台电脑，CPU用的速龙四核系列，主板用的AM3系列，不久CPU风扇不转了。想把风扇拆下来谈何容易？当初是这样考虑的，风扇说明书上宣称是50000小时无故障，也就是说就算每天24小时开机，每年365天天开机，这样计算下来还能用50000/24/365=5.7年，问题谁能用到这种程度啊？平均每天用4小时撑死，这样算下来至少能用34年，就算夸大其辞，只能达到1/10的寿命，也就是3.4年，一般而言电子产品3年后就该淘汰了。鉴于这种幻想，CPU和风扇散热片之间用硅胶导热，没有用硅脂，因为硅脂一般1年左右就干了，需要重新涂抹。(如果你用品牌机，想升级CPU，那注定了CPU很难拆下来。)以上想法是祸患的根源，倒霉的事情发生了，CPU风扇用了半年就不转了，这Made In China的东西质量啊真是没法保证…问题是现在想拆下损坏的风扇谈何容易啊。首先想到的办法是给CPU加热，让硅胶软化，趁热取下。运行稳定性测试程序一段时间后，散热片烫手了，拆下风扇扣具，赶紧带上手套晃动风扇散热片，居然掉下来了，可能用力太大了吧。天呐，我的主板可别坏啊。不过CPU和散热片还是死死的结合在一起，简直就像焊上的一样，这下可麻烦大了…于是就想，导热硅胶耐热但不一定耐冷，找了个防静电袋把散热片和CPU一起装进去放到冰箱里冷冻了一天。第二天取出来，寒气袭人，冰凉冰凉的，带上手套想把C ...继续阅读 (20)

1、一对夫妻总吵架，每次吵架后妻子愤怒的冲进厕，过一会出来一脸的满足感，丈夫甚是纳闷不解。终于有一天问起原因。丈夫：为何每次吵架你那么愤怒冲进厕所，出来却那么满足呢？妻子：你觉得我是在用自己的牙刷刷马桶吗？2、今天一学妹来公司面试，经理看了看简历抬头问她：你是党员？小学妹顿时紧张了起来，激动的说：党员也有好人啊。。。3、和同学去旅游，在寺庙功德箱里赫然看到一张印有古代人头像和仪器的纸币，童鞋勃然大怒，喊到："这素质，不捐就不捐，扔什么冥币！" 我小声提醒："别吵别吵，那是韩元..."4、一个七旬老太捡废品时捡到7000块钱毫不犹豫地将钱交给警方。办完手续后，老人不好意思地问警察："我还没吃早饭，可不可以借一元买两馒头吃？"在场警察震惊了，纷纷掏出口袋里的钱往老人手里塞。老人坚持只要一块钱。望着老人远去的背影，警察们含着热泪把7000 块钱分了。5、"昨天被车撞，还没等司机下车，我就赶紧跑，这样做对吗？"(回复1) 对，不然会被捅死，而且凶手还不能偿命！(回复2) 对，否则可能被来回碾压致死！(回复3) 你没有刺瞎自己双眼再跑吗，误看了车牌怎么办！(回复4) 昨晚我也被车撞，见司机向我走来，我边喊"规矩我懂"边扔下钱包，闭眼爬走。Chipset2011-09-28 09:45发表评论 ...继续阅读 (19)

摘要: STL中的关联容器一般用平衡树来实现，多数是红黑树，平衡树的单个插入、查找、删除操作时间复杂度都为O(logn)，但是为了保证元素之间的相对次 序，每个元素需要三个指针和一个状态位的内存开销，还有，在堆上分配的每块内存都有几个字节的metadata开销。如果用于处理短类型的元素，这实在不划算。况且很多场合我们并不需要频繁插入和删除元素，仅仅是大量检 索操作。 如果仅需要大量查找，且不会频繁的插入和...阅读全文Chipset2011-09-27 19:55发表评论 ...继续阅读 (12)

今天看老外写的文章提到了C#国际标准…什么，C#还有国际标准？不会吧？谷歌一下，果然如此，06年就有了ISO标准…居然还能从ISO官网下载到电子版。看来金钱就是好东西啊，有钱能使鬼推磨道理在地球上哪里都好用…继续谷歌，在MSDN上发现了下面的文字。连接：http://msdn.microsoft.com/en-us/netframework/aa569283In June 2005, the General Assembly of the international standardization organization Ecma approved edition 3 of the C# Language and the Common Language Infrastructure (CLI) specifications, as updated Ecma-334 and Ecma-335, respectively (seepress release). The updated technical report on the CLI, Ecma TR-84, and a new technical report on the CLI, Ecma TR-89, were also ratified.In July 2005, Ecma subm ...继续阅读 (15)

1、 一人在办公室老是放响屁，同事忍不住说：你能不能不出声？然后便见他坐在那摇来晃去抖个不停，问：干什么？回答说：我调成振动的了 ！2、一民工大便不通去医院作检查，医生检查后给此人开了一个药方，民工到取药处一看是一卷手纸，不解，医生说：以后不要再用水泥袋擦屁股了！3、某人第一次见到大海，感叹道：“大海啊！母亲！”话音刚落，一个浪头打过来，正好打在他的脸上，此人怒道：“我靠！还他****是个后妈！4、猴子拣到一个卡，于是爬到树枝上想看清楚是啥卡。不料一个雷击中了它，猴子哭着说：“原来是‘IP’(挨劈)卡呀！！”5、局长与科长共乘电梯，局长放一屁后对科长说：你放屁了！科长说：不是我放的。不久科长被免职。局长在会上说：屁大的事你都担待不起，要你何用？6、在一家时装店，我看到一个等得不耐烦的青年人对一个漂亮女孩说：“你介意和我说几句话吗？”女孩好奇地问：“为什么？”“我妻子进这个店已经一个多小时了，但她 如果看见我和你说话，她会马上出来的......”没等他说完，他妻子已快步走出时装店，挽着他离开了。7、某君开车内急 情急之下尿在空雪碧瓶里 趁堵车时奔下车想把瓶仍到垃圾桶里被一敬职的巡警拦住 瓶里装的啥 喝剩的雪碧 那你喝一口 ...继续阅读 (14)

转贴，已经记不清出处，抱歉。1、儿时，小男孩家很穷，吃饭时，饭常常不够吃，母亲就把自己碗里的饭分给孩子吃。母亲说，孩子们，快吃吧，我不饿！——母亲撒的第一个谎2、男孩长身体的时候，勤劳的母亲常用周日休息时间去县郊农村河沟里捞些鱼来给孩子们补钙。鱼 很好吃，鱼汤也很鲜。孩子们吃鱼的时候，母亲就在一旁啃鱼骨头，用舌头舔鱼骨头上的肉渍。男孩心疼，就把自己碗里的鱼夹到母亲碗里，请母亲吃鱼。母亲不 吃，母亲又用筷子把鱼夹回男孩的碗里。母亲说，孩子，快吃吧，我不爱吃鱼！——母亲撒的第二个谎3、上初中了，为了缴够男孩和哥姐的学费，当缝纫工的母亲就去居委会领些火柴盒拿回家来，晚上 糊了挣点分分钱补点家用。有个冬天，男孩半夜醒来，看到母亲还躬着身子在油灯下糊火柴盒。男孩说，母亲，睡了吧，明早您还要上班呢。母亲笑笑，说，孩子， 快睡吧，我不困！——母亲撒的第三个谎4、高考那年，母亲请了假天天站在考点门口为参加高考的男孩助阵。时逢盛夏，烈日当头，固执的 母亲在烈日下一站就是几个小时。考试结束的铃声响了，母亲迎上去递过一杯用罐头瓶泡好的浓茶叮嘱孩子喝了，茶亦浓，情更浓。望着母亲干裂的嘴唇和满头的汗 珠，男孩将手中的罐头瓶反递过去请母亲喝。母亲说，孩子，快喝吧，我不渴！——母亲撒的四个谎5、父亲病逝之后，母亲又当 ...继续阅读 (15)

读取一个字符窜，该字符窜表示出生年月日，例如19880521表示1988年5月21日，判断这个日期是否合法，看起来似乎十分简单，但是具体做起来却很麻烦，因为一个字符窜中可能未必都是数字，即使都是数字可能月份和日期不正确，例如19861330显然有问题，不应该有13月份，再如19870230，2月份不应该有30天。其实我们只需要实现这样一个功能函数练练练字符窜处理就是了。它表示的范围在1900年1月1日至2099年12月31日之间，当然在这个区间内应该是个理论上合法的日期。基本上可以这样分步来做，先检查字符窜长度是否合法，然后检查是否都是数字，然后检查年份是否合法，然后检查月份和天数是否合法。当然也可以在一起一并检查，只是逻辑上很乱。由于是终端字符窜读取检查，不要求速度一定多快。如果您很久没有写过字符窜处理的C程序了，不妨练练手回忆一下过去学习的知识。下面的C代码(不用C++)有些臃肿，欢迎提出建议和意见。#include// strlen, strncpy#include// isdigit#include// atoiint isValidDate(const char* str){// 检查长度const int LEN = 8;int len = strlen(str);if(LEN != len)return 0;// 检查所有字符是否均为数字int idx = 0;whi ...继续阅读 (9)

有时候用到位运算。需要快速找到一个整数的二进制第一个1或0在哪个位(下标)？例如：十进制数100的二进制是1100100，那么它的第一个1在下标为2的位置(bsf, bit scan forward)或6的位置(bsr, bit scan in reverse order)，由于只用于存储一个状态，至于用bsf还是bsr则无所谓。解决这个问题的第一个想法就是用内联汇编的做法，使用特别的CPU指令去找，但汇编的可移植性比较差，不同的CPU型号使用的指令可能不一样，执行速度也不一样。假设找一个64位无符号整数二进制的第一个1，用bsf, AT& T汇编(gcc汇编)可以这样做：1// bit scan forward for 64 bit integral number2/* ============================================ */3inlineintbsf_asm (uint64_t w)4{5intx1, x2;6asm ("bsf %0,%0\n" "jnz 1f\n" "bsf %1,%0\n" "jz 1f\n" "addl $32,%0\n"7"1:": "=&q;" (x1), "=&q;" (x2):"1" ((int) (w >> 32)),8"0" ((int) w));9returnx1;10}如果用C来实现的话，那就有点麻烦 ...继续阅读 (16)

2007年初，刚刚卸任的联合国秘书长安南，在德克萨斯州的一个庄园里举行了一场慈善晚宴，旨在为非洲贫困儿童募捐。应邀参加晚宴的都是富商和社会名流。在晚宴将要开始的时候，一位老妇人领着一个小女孩来到了庄园的入口处，小女孩手里捧着一个看上去很精致的瓷罐。守在庄园入口处的保安安东尼拦住了这一老一小。“欢迎你们，请出示请柬，谢谢。”。“请柬，对不起，我们没有接到邀请，是她要来，我陪她来的。”老妇人抚摸着小女孩的头。“很抱歉，除了工作人员，没有请柬的人不能进去。”安东尼说。“为什么？这里不是举行慈善晚宴吗？我们是来表示我们的心意的，难道不可以吗？”老妇人的表情很严肃，“可爱的小露西，从电视上知道了这里要为非洲的孩子们举行慈善活动，她很想为那些可怜的孩子做点事，决定把自己储钱罐里所有的钱都拿出来，我可以不进去，真的不能让她进去吗？”“是的，这里将要举行一场慈善晚宴，应邀参加的都是很重要的人士，他们将为非洲的孩子慷慨解囊。很高兴你们带着爱心来到这里，但是，我想这场合不适合你们进去。”安东尼解释说。“叔叔，慈善的不是钱，是心，对吗？”一直没有说话的小女孩问安东尼，她的话让安东尼愣住了。“我知道收到邀请的人有很多钱，他们会拿 ...继续阅读 (20)

2011年8月10日新的C++标准名义上已经顺利通过，因为所有国家都投了赞成票，等正式标准出台还要等一段时间。在这个标准里规定静态变量的线程安全由编译器负责，问题是编译器通常要落后于标准2～3年。这段时间静态变量的线程安全谁来保证？相信很多程序员都会写出自己的代码来保证自己的程序不会有这种隐患。在此总结一下，这篇文章是07年的，今天又回顾了一下，感觉还行，贴在这里。Thread Safe for Static VariablesBy VladimirWhile working on a solution for a fairly narrow and specific problem, I discovered a new synchronization mechanism. This mechanism not only provided a novel and effective solution to my problem, but turns out to have a number of properties making it useful for a wide range of important applications.My original problem had to do with the implementation of Singletons. The ...继续阅读 (18)

关于B+树的实现和测试，我见过的最详细的C++代码在：http://idlebox.net/2007/stx-btree/一位德国朋友的杰作。Chipset2011-08-16 15:05发表评论 ...继续阅读 (26)

摘要: 该比武只比速度，单线程测试随机正整数，不包括蜗牛排序，它弃权啦，哈哈。操作系统：Windows XP Pro SP3，英文版编译器：g++4.5.2(-O3)CPU： Intel Core2 Q9500内存：DDR3普条 1066MHz， 4GB 插入排序、选择排序和冒泡排序最慢，时间复杂度为O(n2)，希尔排序的速度依赖于使用的增量序列，堆排序、归并排序和改进的快速排序处于中等水平，时间复杂度...阅读全文Chipset2011-08-16 14:14发表评论 ...继续阅读 (35)

二分插入排序直接插入排序时后面的元素从后向前逐个比较寻找插入位置，有时候没有必要这样做，因为此时需要寻找合适插入位置的当前这个元素前面的子序列已经有序，如果使用二分查找插入位置往往可以减少平均搜索长度。对于一个待排序的随机序列而言，用二分插入排序取代直接插入排序，尽管总的移动元素次数不可能减少，但是可能减少总的平均比较次数。二分插入排序的平均时间复杂度为O(n2)，最坏情况下的时间复杂度为(n2)，当待排序序列已经有序时，排序时间复杂度为O(nlogn)。空间复杂度为O(1)。二分插入排序是否稳定依赖于具体实现。假设一个序列已经有序，此时我们需要向这个序列里插入一个新的值，那么我们如何找到合适的位置呢？首先跟序列最中间的那个元素比较，如果比最中间的这个元素小，则插入位置在它的左边，否则在它的右边。以当前最中间位置为分割点，如果在左边，则当前最中间位置是待搜索子序列的终点，如果在右边，右边邻接的元素将是待搜索子序列的起点。按照这种原则，继续寻找下一个中间位置，并继续这种过程，直到找到合适的插入位置为止。问题是何谓合适的插入位置？如果序列中有一个元素与当前待插入的元素值相等，那么插入位置应该选在该元素的前面还是后面呢？选在后面则二分插入排序稳定，选在前面则二分插入排序不稳定。如果序列中有多个元素与当前待插入的元素值相等，插入位置选在哪里呢？选在最后一个的后面则二分插入排序稳定，其它情况 ...继续阅读 (16)

桶排序当待排序的随机序列密集的分布于一个狭窄区间时，使用计数排序速度比较快，当待排序的随机序列比较均匀的分布于一个较宽区间时，可以考虑使用桶排序。桶排序的时间复杂度为O(n)，空间复杂度也为O(n)。既然一个待排序的随机序列比较均匀的分布于一个区间，就很容易散列到各个桶中，假设有n个元素比较均匀的散列到m个桶中，则每个桶中的元素数目约为n/m，可以使用普通排序算法对每个桶中的元素排序，排序完毕后再把所有元素复制到最初序列的位置覆盖原始序列。实际应中n/m通常很小，可以使用直接插入排序给每个桶中的元素排序，总的时间复杂度为O(n + m*(n/m)2+ n) = O(n2/m + 2n) = O(n)。如果每个桶的元素用链表存储，链表可以用归并排序，各桶排序完毕后把各个链表连接起来就可以了，省去一次复制元素的麻烦，这样操作的时间复杂度为O(n + m(n/m)log(n/m)) = O(n + nlogk) = O(n)。以随机整数为例，桶排序过程如下表。48 40 66 91 47 68 31 30 29 23 99 35 23 88 88 87待排序的随机序列01 2 3 4 5 6 7 89桶号29 23 23 31 30 3548 40 47 66 68 88 88 8791 ...继续阅读 (16)

计数排序如果给一个分布于区间[min, max)的随机序列排序，可以考虑使用计数排序，max-min越小说明分布越集中，此时使用计数排序效果就越好，计数排序是一种稳定的排序算法。一般而言，计数排序的时间复杂度为O(n)，空间复杂度O(n)，从理论上来看，它比时间复杂度O(nlogn)的算法明显快一些。使用计数排序算法对一个正整数序列进行升序排序时，假设对于某个元素比它小的元素个数为i(其中0≤i，获取该信息无需借助比较运算)，则排序后该元素就应该位于数组下标为i的位置。现在的问题是，如果对于等于某个值的正整数不止一个该如何确定各自位置呢？这个问题在实现中容易解决。为了能够正常排序，需要用max-min个辅助空间记录不同正整数的个数，由于排序无法原地进行，还需要开辟等大的辅助空间容纳排序后的所有正整数，一般而言，max-min不大于待排序的正整数个数或与之相当，可见空间复杂度为O(n + (max-min)) = O(n)。以一个随机整数序列为例，计数排序过程如下。13 11 13 11 13 12 15 17 15待排序序列0 1 23 4 56 7 8计数数组下标1 2 14 0 51 1 1依次计数1 3 48 8 13 14 15 16计数累计10 11 11 12 1 ...继续阅读 (12)