请教：各种排序算法效率的问题

[sdenvi]

大家工作中遇到排序的时候一般采用什么样的一种方式，效率如何？对字符进行排序的时候遇到相同的字符又是采用哪种排序效率比较高？

[jy02201949]

待会又有人来帖教你如何 google 的网址了，话说字符排序是什么情况，字符串么？

[geelaw]

我一般用电脑排，用手排序的时候一半用归并。

[lany]

我一般用 Excel 点一下升序就好了

[xj998]

用 Linux 命令就行了。

[as463419014]

放到数据库里,order by,[手动滑稽]

[coderluan]

单纯研究算法效率就看复杂度呗，工作中遇到肯定是拿来主义，如果真遇到大量数据需要排序，一般都是优先考虑能分解和并行的算法的。

[sdenvi]

@coderluan 今天去面试，面试官问到一个问题，就是给个乱序的字符串，里面可能包含相同的字符，对其进行正序或者倒序排列，是不是应该把字符串中相同的字符先放到一起再去考虑排序的问题？

[coderluan]

这个啊，不是那个 acm 水题吗，只不过把整数换成了字符，这题根本是排序，而是结构转换。
简单来说，就是你弄个 bool 的字母表，先全设置成 0，然后读输入字符串，碰见个字符，就把字母表相应位置，设成 1，重复不重复的无所谓，最后把字母表中为 1 的字符全输出就是结果了，因为字母表本身都是按顺序来的。

[holyghost]

@sdenvi 这个用桶排，时间 O(n)空间 O(1)

[coderluan]

上面说的可能比较混乱，假设字母就有 a,b,c,d,e 五个，那样你开始申请个 A[0] = {0,0,0,0,0}。
碰见了输入 cdbd，那样数组的变化就是 {0,0,1,0,0}， {0,0,1,1,0}， {0,1,1,1,0}， {0,1,1,1,0}最后把 1 的位输出，就是 bcd 了。

[thundernet8]

以数组排序为例，不考虑数值特殊性，用归并排序的迭代方式比较好，时间和空间都控制的不错，在几个常见排序算法里面，接近快排的时间消耗

[starqoq]

@coderluan
@thundernet8
建一棵字母树，然后遍历一下就好了。

[coderluan]

@starqoq #12 用不到树，字符本身就是线性顺序