52被浏览8136分享邀请回答01 条评论分享收藏感谢收起感谢 @&a href=&/people/lzxnd& class=&internal&&基宁&/a& 从百度知道上找到的材料，但或许是微软更改了排序规则,该答案还是有一些错漏之处，于是吾人决定手工测试一下。资历相关：熟练掌握在windows系统图形界面下进行新建文件（夹）、文件（夹）重命名等操作。&br&&br&&b&实验名称&/b&：手工测试 windows 10 英文版 中名称由合法中英文键盘符号（不含\/:*?&&&|）、数字、英文字母与汉字组成的文件（夹）按名称排序（Sort by Name）升序排列时的排序规律&br&&br&先撂图&br&&img src=&/1d364e37529ede9fca6ea042bf552dae_b.png& data-rawwidth=&911& data-rawheight=&683& class=&origin_image zh-lightbox-thumb& width=&911& data-original=&/1d364e37529ede9fca6ea042bf552dae_r.png&&&b&术语表&/b&：（不支持表格就算了，不支持制表符也忍了，连连续空格都不支持是怎么个情况！）&br&A&B ...............................表示A排在B之前&br&前导字符 .........................'-（英文连字符，减号）—（中文破折号）&br&英文键盘符号 ...................!#$%&(),.;@[]^_`{}~+=&br&中文键盘符号 ...................！￥…（）【】、：；“”‘’《》，。？&br&数字 ................................&br&英文字母 ..........................a-zA-Z&br&&br&&b&规则&/b&：&br&00.文件夹&文件，文件先依主名排序，主名相同依扩展名排序。文件夹名、文件主名、扩展名以下统称为「名称」，按下列步骤排序。&br&0.空串&非空串&br&1.忽略名称中的前导字符，将名称视为以下子串的拼接，自左向右依次比较所有子串：纯符号串、纯数字串、纯英文字母串、纯汉字串&br&1.1.首先按子串的类型排序：符号&数字&英文字母&汉字&br&1.2.类型相同的，按下列规则排序：&br&&b&键盘符号&/b&：自左向右对位比较，英文键盘符号顺序为!#$%&(),.;@[]^_`{}~+=，中文全角符号一般跟随在对应英文符号之后，混排顺序为!！#$%&(（)）,，、.。;；？@[]^_`{}~‘’“”《》￥【】+=·…&br&&b&数字&/b&：按数值大小由小到大排列，同等大小按前导零数目由多到少排列。（win 7可以在组策略中启用“关闭Windows资源管理器中的数值排序”将此规则更改为按每个数字位依次比较排序，其它版本未确认）&br&&b&英文字母&/b&：自左向右对位比较，按a-z的顺序排列，不区分大小写&br&&b&汉字&/b&：自左向右对位比较，根据系统当前的语言识别码（LCID，Windows Language Code Identifier）排序。LCID确定了系统语言格式和排序方法。比如简体中文可用的排序有拼音、姓氏和笔画数：日文可用的有XJIS和部首。这些设置可以在 “控制面板-区域-格式-排序” 中更改。没有特殊排序方式的语言格式（比如英语）依Unicode编码的code point排序。参考：&a href=&///?target=http%3A///question/484027/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Windows 资源管理器是如何排序文件...&i class=&icon-external&&&/i&&/a&
与 &a href=&///?target=https%3A///en-us/library/cc233970.aspx& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&[MS-LCID]: Glossary&i class=&icon-external&&&/i&&/a&&br&多语言混排的非Unicode排序规则尚不清楚，因为答主就是不清楚。&br&&br&2.忽略前导字符后完全相同的，按以下规则自左到右依次比较对应前导字符串：&b&自右向左&/b&对位比较，顺序为'&-&—&br&&br&以上规则均可在测试图中找到对应实例验证。&br&&br&更多非键盘直接输入的Unicode符号未经测试，因为数量太多，而且可以看出Microsoft试图在用一种更加有意义的顺序而不是简单的按位比较code point来排序这些符号，比如测试图中的 1/2 被放在0和1之间……吐槽不能。&br&&br&&b&如何命名？&/b&&br&1.参照传统纸质文件（夹）命名方法。把文件内容、时间、来源或其它必要信息写清楚。这是最先要做的。&br&2.添加前后缀实现想要的排序效果。&br&比如 ' 和 - 很适合用来在文件名前后标识同一文件的不同版本，比如 绝对最终版.pdf 和 -绝对最终版.pdf 和 绝对最终版'.pdf 甚至 ----------------'绝'对'最'终'版'''''''''''''.pdf 都会紧紧的挨在一起的。&br&答主用 ! 来提前和固定重要的项目，前缀 ! 可以对对象施加永久性“排列在前端”效果，这样想觉得好魔法（其实 ! 本来就被广泛用于标记重要项目）。
感谢 @ 从百度知道上找到的材料，但或许是微软更改了排序规则,该答案还是有一些错漏之处，于是吾人决定手工测试一下。资历相关：熟练掌握在windows系统图形界面下进行新建文件（夹）、文件（夹）重命名等操作。 实验名称：手工测试 windows 10 英文版 …
&p&我也常问这种面试问题，基本上回答有这几种：&/p&&p&直接上来说，简单，用这个算法那个算法 用这个集群那个集群的，直接turn down&/p&&p&询问细节的，问 需要获得热搜前十名到底是什么啊？一秒刷新一次是客户端端到端还是怎样啊？这些属于上手能干活的，放到中级资源池，扔给后面项目自己挑&/p&&p&上来问infra的，问你的多少服务器啊，你的网络是怎么样的，你的集群怎么做啊？ 这是架构师或者架构师苗子，留在自己的组培养着。&/p&
我也常问这种面试问题，基本上回答有这几种：直接上来说，简单，用这个算法那个算法 用这个集群那个集群的，直接turn down询问细节的，问 需要获得热搜前十名到底是什么啊？一秒刷新一次是客户端端到端还是怎样啊？这些属于上手能干活的，放到中级资源池，…
你好像没有理解排序稳定性的意思，稳定是指排序前后相同值的相对位置不变，而不是多次排序的结果中相同值的相对位置不变。
你好像没有理解排序稳定性的意思，稳定是指排序前后相同值的相对位置不变，而不是多次排序的结果中相同值的相对位置不变。
&p&很有意思的一个问题，通过16次比较确实是有解的，《计算机程序设计艺术》(俗称TAOCP)里面提到了一种叫做&合并插入排序&的方法：&/p&&ol&&li&首先将8个小球划分成4对，通过 &b&4&/b& 次比较我们可以得到 &img src=&///equation?tex=b_1+%5Cleq+a_1& alt=&b_1 \leq a_1& eeimg=&1&&, &img src=&///equation?tex=b_2+%5Cleq+a_2& alt=&b_2 \leq a_2& eeimg=&1&&, &img src=&///equation?tex=b_3+%5Cleq+a_3& alt=&b_3 \leq a_3& eeimg=&1&&, &img src=&///equation?tex=b_4+%5Cleq+a_4& alt=&b_4 \leq a_4& eeimg=&1&&；&/li&&li&对 &img src=&///equation?tex=a_1& alt=&a_1& eeimg=&1&&, &img src=&///equation?tex=a_2& alt=&a_2& eeimg=&1&&, &img src=&///equation?tex=a_3& alt=&a_3& eeimg=&1&&, &img src=&///equation?tex=a_4& alt=&a_4& eeimg=&1&& 排序，通过 &b&5&/b& 次比较（这里应该没有问题，用归并排序就可以），假设最后我们得到 &img src=&///equation?tex=a_1+%5Cleq+a_2+%5Cleq+a_3+%5Cleq+a_4& alt=&a_1 \leq a_2 \leq a_3 \leq a_4& eeimg=&1&&，此时集合 &img src=&///equation?tex=%5Cleft%5C%7B+b_1%2Ca_1%2Ca_2%2Ca_3%2Ca_4+%5Cright%5C%7D& alt=&\left\{ b_1,a_1,a_2,a_3,a_4 \right\}& eeimg=&1&& 的所有元素顺序确定;&/li&&li&现在考虑插入 &img src=&///equation?tex=b_3& alt=&b_3& eeimg=&1&& (对的你没看错，不是 &img src=&///equation?tex=b_2& alt=&b_2& eeimg=&1&& )，因为 &img src=&///equation?tex=b_3+%5Cleq+a_3& alt=&b_3 \leq a_3& eeimg=&1&&, 所以只需二分查找它在集合 &img src=&///equation?tex=%5Cleft%5C%7B+b_1%2Ca_1%2Ca_2+%5Cright%5C%7D& alt=&\left\{ b_1,a_1,a_2 \right\}& eeimg=&1&& 中的位置然后插入，需要 &b&2&/b& 次比较，此时集合 &img src=&///equation?tex=%5Cleft%5C%7B+b_1%2Ca_1%2Ca_2%2Cb_3%2Ca_3%2Ca_4+%5Cright%5C%7D& alt=&\left\{ b_1,a_1,a_2,b_3,a_3,a_4 \right\}& eeimg=&1&& 的所有元素顺序确定;&/li&&li&这时候再考虑插入 &img src=&///equation?tex=b_2& alt=&b_2& eeimg=&1&&, 因为 &img src=&///equation?tex=b_2+%5Cleq+a_2& alt=&b_2 \leq a_2& eeimg=&1&&， 因此至多需要在集合 &img src=&///equation?tex=%5Cleft%5C%7B+b_1%2Ca_1%2Cb_3+%5Cright%5C%7D& alt=&\left\{ b_1,a_1,b_3 \right\}& eeimg=&1&& 中二分查找然后插入，需要 &b&2&/b& 次比较，此时集合 &img src=&///equation?tex=%5Cleft%5C%7B+b_1%2Ca_1%2Cb_2%2Ca_2%2Cb_3%2Ca_3%2Ca_4+%5Cright%5C%7D& alt=&\left\{ b_1,a_1,b_2,a_2,b_3,a_3,a_4 \right\}& eeimg=&1&& 的所有元素顺序确定；&/li&&li&最后插入 &img src=&///equation?tex=b_4& alt=&b_4& eeimg=&1&&, 此时需要在集合 &img src=&///equation?tex=%5Cleft%5C%7B+b_1%2Ca_1%2Cb_2%2Ca_2%2Cb_3%2Ca_3+%5Cright%5C%7D& alt=&\left\{ b_1,a_1,b_2,a_2,b_3,a_3 \right\}& eeimg=&1&& 中二分查找它的插入位置然后插入，需要 &b&3&/b& 次比较，此时集合 &img src=&///equation?tex=%5Cleft%5C%7B+b_1%2Ca_1%2Cb_2%2Ca_2%2Cb_3%2Ca_3%2Cb_4%2Ca_4+%5Cright%5C%7D& alt=&\left\{ b_1,a_1,b_2,a_2,b_3,a_3,b_4,a_4 \right\}& eeimg=&1&& 顺序确定，排序完成！&/li&&/ol&&p&统计一下比较次数
&b&4 + 5 + 2 + 2 + 3 = 16&/b&，不多不少！&/p&&p&最后解释一下最违反常理的一点吧，为什么要先插入 &img src=&///equation?tex=b_3& alt=&b_3& eeimg=&1&& 而不是 &img src=&///equation?tex=b_2& alt=&b_2& eeimg=&1&&, 这也是&合并插入排序&的精髓所在，总结起来一句话：&/p&&blockquote&&i&在 &img src=&///equation?tex=x& alt=&x& eeimg=&1&&个有序元素中 (&img src=&///equation?tex=2%5E%7Bn-1%7D+%5Cleq+x+%3C+2%5En& alt=&2^{n-1} \leq x & 2^n& eeimg=&1&&) 二分查找插入的位置，都只需要 &img src=&///equation?tex=n& alt=&n& eeimg=&1&& 次比较。&/i&&/blockquote&&p&&合并插入排序&本质上就是最大限度地利用好这个性质以减少比较次数。&/p&&p&&/p&&p&&/p&
很有意思的一个问题，通过16次比较确实是有解的，《计算机程序设计艺术》(俗称TAOCP)里面提到了一种叫做"合并插入排序"的方法：首先将8个小球划分成4对，通过 4 次比较我们可以得到 b_1 \leq a_1, b_2 \leq a_2, b_3 \leq a_3, b_4 \leq a_4；对 a_1, a_2, …
并不是按照ASCII码排序的，刚才测试了一下- -
注意 文件名中不能包含 \ / : * ? & & & | 因此将这几个符号排除测试范围 英文字符及数字字母排列顺序为： ! # $ % & ( ) , . ' - ; @ [ ] ^ _ ` { } ~ + = 0 1 2 … 9 A B C … Z 系统不区分大小写字母
刚才测试了一下中文字符，日语假名，汉字，部分其他语种等 中文英文日文字符混编顺序如下（半角） ! ！ # $ % & ( （ ) ） , ， . ' - — 。 ： ; ； @ [ ] ^ _ ` { } ~ ～ ‘ “ 《 》 ￥ 『 』 【 】 + = × ÷ · … 0 1 2 9 A B C Z
吖 啊 八 压 作 （汉字应该是按照拼音排序，如果是多音字，则取其中一种发音作为排序音）
经过测试，日文假名排在汉字之前，其排序规则如下 （无论平片假名按照五十音图排列，不过浊音与半浊音排列在ya、wa、n等音前，且同一假名中片假名位于平假名前）
经过测试，绝大多数韩文字符排列在汉字之后，粗略测试只有子音?排在汉字之前 韩文字母、复合字母及单字均按照其第一个构成字母排序，第一个相同按照第二个，以此类推 排序方式是从子音 ? 到 ? 然后是母音 ? 到 ? （由于韩语只学了皮毛，因此我的判断并不一定准确）
经过测试，希腊语字符排在英文字母之后，日语假名之前，且按照希腊语字母标准排序方式排列，并且不区分大小写
经过测试阿拉伯语字符排列在日文假名之后，汉字及韩文之前 （由于没学过阿拉伯语，因此无从判断阿拉伯语字符排序方式）
由于时间关系，先是测试了这些字符排序方式
关于数学等专用符号，经过简单测试混杂于英文字符及中文字符后半段，甚至有些混杂到数字以及英文字母中 以下是其中几个专用符号插在中英文普通标点中的排序位置（因为数量实在庞大，无法全部测试，只能选择了几个） 【 】 + = ≠ ± × ÷ ∴ ∵ ≈ △ ◆ ◇ ○ ◎ ● ↑ → ↓ ← § · … 〓 ☆ ★ 0 1 2 3 9 ∞ A B C M N Na Nz № O P Z &br&参考：&a href=&///?target=http%3A///question/.html& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/questi&/span&&span class=&invisible&&on/.html&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&
并不是按照ASCII码排序的，刚才测试了一下- - 注意 文件名中不能包含 \ / : * ? " & & | 因此将这几个符号排除测试范围 英文字符及数字字母排列顺序为： ! # $ % & ( ) , . ' - ; @ [ ] ^ _ ` { } ~ + = 0 1 2 … 9 A B C … Z 系统不区分大小写字母 刚才测…
内存装得下用三向切分快速排序，内存装不下用归并排序。&br&&br&重复元素不多是普通的快速排序即可，重复元素很多时三向切分快速排序性能更佳。&br&&br&&b&空间复杂度&/b&&br&归并排序的空间复杂度不是最优的，需要另外一个数组来存放排序结果。对于大数据可以考虑用输入输出流。&br&快速排序是原地排序。&br&&br&&b&时间复杂度&/b&&br&归并排序比快速排序稳定，二者理性情况下的时间复杂度都是&img src=&///equation?tex=NlgN& alt=&NlgN& eeimg=&1&&。&br&快速排序的平均时间复杂度是&img src=&///equation?tex=2NlnN%5Capprox+1.39NlgN& alt=&2NlnN\approx 1.39NlgN& eeimg=&1&&，最坏情况&img src=&///equation?tex=N%5E%7B2%7D+%2F2& alt=&N^{2} /2& eeimg=&1&&。&br&归并排序一般都比较趋向于&img src=&///equation?tex=NlgN& alt=&NlgN& eeimg=&1&&&br&&br&&b&求MAX(N)或者MIN(N)&/b&&br&如果仅仅是寻找大数据中最大或者最小的N个元素，不需要全局排序，采用优先队列即可。&br&&br&&b&语言内置的排序算法&/b&&br&java.util.Arrays.sort()&br&对于原始类型使用（三向切分的）快速排序，对于引用类型使用归并排序&br&python sort&br&早期版本采用快速排序，2.3版本以后采用了timsort（一种适应性归并排序）&br&Ruby Array.sort&br&采用native实现的快速排序
内存装得下用三向切分快速排序，内存装不下用归并排序。 重复元素不多是普通的快速排序即可，重复元素很多时三向切分快速排序性能更佳。 空间复杂度 归并排序的空间复杂度不是最优的，需要另外一个数组来存放排序结果。对于大数据可以考虑用输入输出流。 快…
1. matlab 写的快排比 C 写的慢大概 20 倍&br&&br&2. 默认的 sort 不是纯粹的快排，它包括了&br&2.1 数据量比较小的时候用 猫泡 排序&br&&img data-rawheight=&768& data-rawwidth=&1024& src=&/bcba044ee637e96acfbfa85_b.png& class=&origin_image zh-lightbox-thumb& width=&1024& data-original=&/bcba044ee637e96acfbfa85_r.png&&[图片：猫泡排序示意图]&br&2.2 pivot 不能很好的分割两边的时候，使用堆排序&br&&br&3. 不是特别重要的一个：默认的 sort 的 pivot 不仅仅是首尾，我记得是首尾和中间取一个&br&4. 我不知道是否重要：你试着用 -nodesktop 运行一下？&br&我记得你可以参考 GCC 或者 Borland 默认的 CPP STL 的 sort，现在 VS 的 sort 怎样我不清楚
1. matlab 写的快排比 C 写的慢大概 20 倍 2. 默认的 sort 不是纯粹的快排，它包括了 2.1 数据量比较小的时候用 猫泡 排序 [图片：猫泡排序示意图] 2.2 pivot 不能很好的分割两边的时候，使用堆排序 3. 不是特别重要的一个：默认的 sort 的 pivot 不仅仅是…
我是这么理解的：基数排序，又称为bucket sort，因为Hollerith当时的人们是拿着真的桶进行排序的。如果数字从高位开始排序，意味着有n位，就得有10^n个桶。因为你先排最高位，然后对于这个最高位又要分出十个桶排下一位。比如现在有13，23，12，22，11这五个数。你先为高位排序，就相当于把十位为1的分在一个桶1里（13，12，11），十位为2的分在一个桶2（22，23）里。然后在桶1和桶2之中剩下的元素排序（（11），（12），（13））和（（22），（23））。这样如果有很多位数，桶就很多。但是从最低位开始排就只需要10个桶，每移动一位，就用针对那一位排序（把元素扔进桶里）。所以不会占用大量的桶。所以，低位排序优于高位排序。
我是这么理解的：基数排序，又称为bucket sort，因为Hollerith当时的人们是拿着真的桶进行排序的。如果数字从高位开始排序，意味着有n位，就得有10^n个桶。因为你先排最高位，然后对于这个最高位又要分出十个桶排下一位。比如现在有13，23，12，22，11这五…
海量数据 还 内存足够大，这明显是矛盾的两个条件
海量数据 还 内存足够大，这明显是矛盾的两个条件
电脑摇号这类业务，我曾经参与过，但仅是在做助理的时候协助公证员办理过，因为都是现场摇号，时刻都是提着一颗心，怕摇出来重号或者少摇、多摇号。在自己成为公证员后，这类业务我是绝对不接的，至于原因，很简单，不懂，也没法控制。&br&题主给的一系列程序和说明，我只能说是理想化的，但凡事就怕认真二字，真的按这些程序和说明要求的去做，我认为公证处的力量是很难达到的。&br&那么第三方技术机构能否协助?我认为这还是一个国家资质的问题，如果没有正式的国家资质，在当前国情下紧靠民间力量是无法确保技术上是完全没问题的。&br&具体就电脑摇号，我本人的认识主要是以下三点：&br&1、摇号软件的研发以及安全性。&br&一个软件是否可靠，首先要看研发人，一旦没有清楚明确的研发人，那么起码是无法追究责任的。其次，在有了明确的研发人，确认研发人资质的前提下，软件程序的可靠性也是关键问题，相应的检测检验机构目前尚没有很明确的界定。以上问题如果无法解决，是无法出现国家标准的，何谈安全。&br&2、软件的运行设备及环境。&br&摇号软件必须通过电脑设备或其他载体才可以应用，因此对设备和载体的安全可靠性也是关键。公证处目前可以依靠封存方式确保无关人员无法解除到这些设备和载体，但也仅仅是形式上的，公证员不可能是电脑专业的专家，对电脑在封存前、封存后的技术检查基本无法保证。公证处最多只能依靠第三方技术进行鉴定，但正如以上说的，这个也是没有国家标准的。&br&3、软件的运行环境及操控。&br&软件的运行分网络环境和单机环境两种，因此可能会产生场外操控的情况。现如今电脑系统的复杂程度之高，即使电脑技术方面的公司、机构，我想也需要很多时间去检测，而在软件运行时能否达到实时监控，确保没有作弊，公证员基本无能为力。&br&以上几个问题，任何一点被做手脚都会造成摇号被操控。&br&另外说说我可以接手的摇号，那就是纯手工抽签类的摇号，虽然麻烦和土鳖，但至少整个环节靠人力是能亲自监督的。
电脑摇号这类业务，我曾经参与过，但仅是在做助理的时候协助公证员办理过，因为都是现场摇号，时刻都是提着一颗心，怕摇出来重号或者少摇、多摇号。在自己成为公证员后，这类业务我是绝对不接的，至于原因，很简单，不懂，也没法控制。 题主给的一系列程序…
首先我们证明这个下界是可以得到的。&br&对于n个输入，进行如下操作：&br&&ol&&li&我们将他两两配对进行一次比较，每个配对的胜者放入等待队列；&/li&&li&如果出现未配对的数，放入等待队列；&/li&&li&对等待队列当作新的输入，跳转到1，递归执行，直到输入大小为1&/li&&/ol&此时剩下的数为最大数，整个比较过程可以看作一个只有0度和2度节点的胜者树，叶子节点就是原始的输入，头节点就是最后的最大值，每个2度节点都代表一次比较。根据这种只有0度和2度节点树的特性，内部节点刚好有n-1个，所以获得最大值需要n-1次操作。&br&现在我们来获得第二大的数，这个数有一个性质：他一定与最大数比较过，且是所有与最大数比较过的数中的最大数。为了得到第二大的数，我们只需要收集最大数在整棵胜者树中路径所有的兄弟节点，并在此调用一次最大数算法，即可得到第二大的数。由于当前胜者树的形状，最大数的所有兄弟节点个数不会超过&img src=&///equation?tex=%5Clceil+lgn+%5Crceil& alt=&\lceil lgn \rceil& eeimg=&1&&,所以得到第二大数的比较次数不会超过 &img src=&///equation?tex=%5Clceil+lgn%5Crceil+-1& alt=&\lceil lgn\rceil -1& eeimg=&1&&。因此，我们可以在&img src=&///equation?tex=n%2B%5Clceil+lgn+%5Crceil+-2& alt=&n+\lceil lgn \rceil -2& eeimg=&1&&比较内得到第二大的数。&br&现在我们来证明最少需要&img src=&///equation?tex=n%2B%5Clceil+lgn+%5Crceil+-2& alt=&n+\lceil lgn \rceil -2& eeimg=&1&&次比较才能得到第二大的数。&br&为了得到第二大的数，我们首先需要得到最大的数，然后将所有与最大数比较过的数中找到最大值，即是第二大。为了得到最小比较次数，所有在比较过程中已经输过的数没有必要再参加比较。整个选取最大数的过程也是一个胜者树，这棵树有2n-1个节点。这棵胜者树中，任何一条从叶子节点到头节点的路径都可能是最大数的比较路径，最坏情况下，第二大数的候选集合大小为最长路径长度-1，额外的比较次数为最长路径长度-2，此时.对于任何一个含有k个节点的二叉树，其最长路径至少为&img src=&///equation?tex=%5Clceil+lg%28k%2B1%29%5Crceil+& alt=&\lceil lg(k+1)\rceil & eeimg=&1&&，所以胜者树中最长路径最短长度为&img src=&///equation?tex=%5Clceil+lg%282n%29%5Crceil%3D%5Clceil+lg%28n%29%5Crceil+%2B1& alt=&\lceil lg(2n)\rceil=\lceil lg(n)\rceil +1& eeimg=&1&&,所以第二大数的候选集合大小在任何情况下都不可能低于&img src=&///equation?tex=%5Clceil+lg%28n%29%5Crceil& alt=&\lceil lg(n)\rceil& eeimg=&1&&。因此获得第二大数所需比较次数最少为&img src=&///equation?tex=n-1+%2B%5Clceil+lg%28n%29%5Crceil+-1%3Dn%2B%5Clceil+lg%28n%29%5Crceil+-2& alt=&n-1 +\lceil lg(n)\rceil -1=n+\lceil lg(n)\rceil -2& eeimg=&1&&.&br&综上，获得第二大数所需比较次数的下界即为&img src=&///equation?tex=n%2B%5Clceil+lg%28n%29%5Crceil+-2& alt=&n+\lceil lg(n)\rceil -2& eeimg=&1&&。
首先我们证明这个下界是可以得到的。 对于n个输入，进行如下操作： 我们将他两两配对进行一次比较，每个配对的胜者放入等待队列；如果出现未配对的数，放入等待队列；对等待队列当作新的输入，跳转到1，递归执行，直到输入大小为1此时剩下的数为最大数，整…
我所看到的语法书有关定冠词的部分都没有提到这种特定的用法是否正确。不过在书籍索引、列出参考书目量很大时较常见。大家都这么用，就是正确的。其好处是，如果都以the开头，实际上是很笨的办法，找东西会很麻烦。谢邀。
我所看到的语法书有关定冠词的部分都没有提到这种特定的用法是否正确。不过在书籍索引、列出参考书目量很大时较常见。大家都这么用，就是正确的。其好处是，如果都以the开头，实际上是很笨的办法，找东西会很麻烦。谢邀。
&b&锦标赛&/b&的方法，这是一种分治的思想。&br&&br&先从最简单的找最小数谈起。&br&对于从N个数中找到最小数，比较容易理解必须比较N-1次，才能知道某数是最小的。&br&在这里其实有一个隐含信息，&b&&u&最小数和第二小数必然已经比较过了&/u&&/b&。&br&&br&所以想继续找到第二小的数，可以缩小第二次查找的范围，仅仅从&b&&u&已经和最小数比较过的集合A&/u&&/b&里进行查找。那么如何才能尽可能的缩小集合A的大小呢？——分治。&br&&br&对数组a[1…n]中元素&b&成对&/b&的做比较，每次比较后将较小的数拿出，形成新的数组再继续这样处理，直到剩下最后的一个，就是数组中最小的那个。将比较的过程以一个树的形式表现出来，如下图： &br&&img src=&/d32ebfe60b6d2c488daebecead9ccbd0_b.jpg& data-rawwidth=&475& data-rawheight=&272& class=&origin_image zh-lightbox-thumb& width=&475& data-original=&/d32ebfe60b6d2c488daebecead9ccbd0_r.jpg&&&br&树中蓝色的节点就是和最小数1比较过的节点，我们可以发现每层只存在一次比较，因此如上文所述的集合A的最小值为
&b&树的深度-1
&b&logN-1.&/b&&br&&br&通过空间换时间的方式，将每个数比较过的数以链表的方式存储下来，这个链表后边的值也就是集合A了。如下图：&br&&img src=&/8f9d43bb4a9d95b50f1db5_b.jpg& data-rawwidth=&350& data-rawheight=&110& class=&content_image& width=&350&&&br&&br&所以最终的最少比较次数为 (N - 1) + (logN -1) = N + logN - 2.
(左括号是找最小所需次数，右边括号里是找第二小所需的次数）
锦标赛的方法，这是一种分治的思想。 先从最简单的找最小数谈起。 对于从N个数中找到最小数，比较容易理解必须比较N-1次，才能知道某数是最小的。 在这里其实有一个隐含信息，最小数和第二小数必然已经比较过了。 所以想继续找到第二小的数，可以缩小第二次…
谢邀。从高位可以，但是麻烦啊。&br&&br&道理是基数排序每次都调用一个稳定排序，也就是说这一轮比不出大小的数据，保持原来的相对顺序不变。而数字比较大小就是从高位开始，比不出大小去看低位，当然应该让低位先排出“原来的相对顺序”了。&br&&br&从高位开始排，就要分段了，每排完一位，把分不出大小的几个当成一段，一段段的排，不要让排完的数据跨段移动，保证这一段的数都比下一段小，排到最后每段就只有一个数了。这样就完全没有利用到每次调用的都是稳定排序这一点，感觉上丑多了，也没什么意思。
谢邀。从高位可以，但是麻烦啊。 道理是基数排序每次都调用一个稳定排序，也就是说这一轮比不出大小的数据，保持原来的相对顺序不变。而数字比较大小就是从高位开始，比不出大小去看低位，当然应该让低位先排出“原来的相对顺序”了。 从高位开始排，就要分…
在jdk8中，如果你看过源码就会知道，其实针对不同的情况使用了不同的排序算法，简单罗列下：&br&1.如果是简单对象数据，例如int，double，且数组长度在一定阀值内，则使用快排，如果在阀值外，则用归并&br&2.如果是复杂对象数组，则如果数组长度在一定阀值以内，则使用折半插入排序，如果长度在阀值外，则使用归并法，但是如果归并二分后小于阀值了，则在内部还是会使用折半插入排序&br&。。。以上只是大概&br&那么为什么复杂对象不使用快速排序呢？因为对于一个hashcode计算复杂的对象来说，移动的成本远低于比较的成本
在jdk8中，如果你看过源码就会知道，其实针对不同的情况使用了不同的排序算法，简单罗列下： 1.如果是简单对象数据，例如int，double，且数组长度在一定阀值内，则使用快排，如果在阀值外，则用归并 2.如果是复杂对象数组，则如果数组长度在一定阀值以内，…
知乎的回答是按粉丝数排序，或者说按大V点赞数排序，跟质量没关系，君不见你的答案被多位大V翻牌后赞数就刷刷地升，大V的答案就是放个屁都有几百个点赞，点赞数压过踩的人了，就自然排前面了，没办法，知乎也是个社会，社会就是这样。
知乎的回答是按粉丝数排序，或者说按大V点赞数排序，跟质量没关系，君不见你的答案被多位大V翻牌后赞数就刷刷地升，大V的答案就是放个屁都有几百个点赞，点赞数压过踩的人了，就自然排前面了，没办法，知乎也是个社会，社会就是这样。
&p&先确定一下量级：&/p&&p&数据量百万级别指的是系统累计一共有几百万的搜索词还是一秒钟有几百万次搜索（貌似一秒钟不应该几百万次搜索）？&/p&&p&默认第一种，做出以下假定，如果一秒钟几万次搜索（一天几十亿次, 百度搜索的pv量级）并且这一秒钟的搜索落在1万个左右的独立词上面（&b&&i&如果这个量级前提不正确，请告知&/i&&/b&）。&/p&&p&可以考虑用最大堆，建立一个几百万个词的堆，一秒钟更新一次，时间复杂度是KlogN，N是几百万，K是一万个词（通过内存hash合并之后1秒钟一次性批量更新）。。。&/p&&p&单核，内存模式，堆的数据结构就可以搞定，如果时间常数上差一些，可以考虑多实例（每个实例1个核不到1G内存），比如3个实例每个实例存1/3份搜索词（一致性hash来分发）, 然后综合3个实例的top10就是整体的top10。有时间找redis的zlist测一下。 &/p&&p&&b&小压测（本人水平很菜，见笑了）：&/b&&/p&&p&由于上面涉及到非正规的最大堆操作（需要随机修改其中一个元素的值, 处理比较麻烦)，所以这里使用redis的zlist（跳跃表）， 本人不是很熟悉java，用python写个demo测了一下，1秒1万个key的更新是没问题的，3万个（比原先预估的1万个key要好很多）key估计就是单个redis实例的极限，如果不够可以考虑使用多实例redis，然后合并多个实例的top 10，忽略数据倾斜的影响（应该不会对算法时间产生较大影响）&/p&&div class=&highlight&&&pre&&code class=&language-python&&&span class=&c&&#!/usr/bin/env python&/span&
&span class=&c&&# -*- coding:utf-8 -*-&/span&
&span class=&kn&&import&/span& &span class=&nn&&redis&/span&
&span class=&kn&&import&/span& &span class=&nn&&random&/span&
&span class=&kn&&import&/span& &span class=&nn&&time&/span&
&span class=&n&&r&/span& &span class=&o&&=&/span& &span class=&n&&redis&/span&&span class=&o&&.&/span&&span class=&n&&Redis&/span&&span class=&p&&(&/span&&span class=&s&&&localhost&&/span&&span class=&p&&,&/span& &span class=&mi&&6379&/span&&span class=&p&&)&/span& &span class=&c&&#单实例redis，2.7 GHz Intel Core i5&/span&
&span class=&k&&def&/span& &span class=&nf&&insert_test_data&/span&&span class=&p&&():&/span&
&span class=&n&&l&/span& &span class=&o&&=&/span& &span class=&p&&[]&/span&
&span class=&k&&for&/span& &span class=&n&&i&/span& &span class=&ow&&in&/span& &span class=&nb&&range&/span&&span class=&p&&(&/span&&span class=&mi&&5000000&/span&&span class=&p&&):&/span& &span class=&c&&#insert 5 million key&/span&
&span class=&n&&l&/span&&span class=&o&&.&/span&&span class=&n&&append&/span&&span class=&p&&(&/span&&span class=&s&&&k_&&/span& &span class=&o&&+&/span& &span class=&nb&&str&/span&&span class=&p&&(&/span&&span class=&n&&i&/span&&span class=&p&&))&/span&
&span class=&n&&l&/span&&span class=&o&&.&/span&&span class=&n&&append&/span&&span class=&p&&(&/span&&span class=&n&&random&/span&&span class=&o&&.&/span&&span class=&n&&randint&/span&&span class=&p&&(&/span&&span class=&mi&&1&/span&&span class=&p&&,&/span& &span class=&mi&&&/span&&span class=&p&&))&/span&
&span class=&k&&if&/span& &span class=&nb&&len&/span&&span class=&p&&(&/span&&span class=&n&&l&/span&&span class=&p&&)&/span& &span class=&o&&==&/span& &span class=&mi&&20000&/span&&span class=&p&&:&/span&
&span class=&n&&begin&/span& &span class=&o&&=&/span& &span class=&n&&time&/span&&span class=&o&&.&/span&&span class=&n&&time&/span&&span class=&p&&()&/span&
&span class=&n&&r&/span&&span class=&o&&.&/span&&span class=&n&&zadd&/span&&span class=&p&&(&/span&&span class=&s&&&search_rank_zlist&&/span&&span class=&p&&,&/span& &span class=&o&&*&/span&&span class=&n&&l&/span&&span class=&p&&)&/span&
&span class=&k&&print&/span& &span class=&n&&time&/span&&span class=&o&&.&/span&&span class=&n&&time&/span&&span class=&p&&()&/span& &span class=&o&&-&/span& &span class=&n&&begin&/span&&span class=&p&&,&/span& &span class=&n&&i&/span& &span class=&c&&# 0.06s ~ 0.12s&/span&
&span class=&n&&l&/span& &span class=&o&&=&/span& &span class=&p&&[]&/span&
&span class=&k&&def&/span& &span class=&nf&&insert_new_data&/span&&span class=&p&&():&/span&
&span class=&n&&begin&/span& &span class=&o&&=&/span& &span class=&n&&time&/span&&span class=&o&&.&/span&&span class=&n&&time&/span&&span class=&p&&()&/span&
&span class=&n&&pipeline&/span& &span class=&o&&=&/span& &span class=&n&&r&/span&&span class=&o&&.&/span&&span class=&n&&pipeline&/span&&span class=&p&&()&/span&
&span class=&n&&KEY_LEN&/span& &span class=&o&&=&/span& &span class=&mi&&30000&/span& &span class=&c&&# 测试30000个key的独立更新情况，此步骤和下面的execute可以异步，核心压力卡在execute上面&/span&
&span class=&k&&for&/span& &span class=&n&&i&/span& &span class=&ow&&in&/span& &span class=&nb&&range&/span&&span class=&p&&(&/span&&span class=&n&&KEY_LEN&/span&&span class=&p&&):&/span&
&span class=&n&&pipeline&/span&&span class=&o&&.&/span&&span class=&n&&zincrby&/span&&span class=&p&&(&/span&&span class=&s&&&search_rank_zlist&&/span&&span class=&p&&,&/span& &span class=&s&&&k_&&/span&&span class=&o&&+&/span& &span class=&nb&&str&/span&&span class=&p&&(&/span&&span class=&n&&i&/span&&span class=&p&&),&/span& &span class=&n&&random&/span&&span class=&o&&.&/span&&span class=&n&&randint&/span&&span class=&p&&(&/span&&span class=&mi&&1&/span&&span class=&p&&,&/span& &span class=&mi&&2000&/span&&span class=&p&&))&/span&
&span class=&k&&print&/span& &span class=&n&&time&/span&&span class=&o&&.&/span&&span class=&n&&time&/span&&span class=&p&&()&/span& &span class=&o&&-&/span& &span class=&n&&begin&/span& &span class=&c&&#0.18s if KEY_LEN = 30000&/span&
&span class=&n&&begin2&/span& &span class=&o&&=&/span& &span class=&n&&time&/span&&span class=&o&&.&/span&&span class=&n&&time&/span&&span class=&p&&()&/span&
&span class=&n&&pipeline&/span&&span class=&o&&.&/span&&span class=&n&&execute&/span&&span class=&p&&()&/span& &span class=&c&&#核心时间消耗&/span&
&span class=&n&&res&/span& &span class=&o&&=&/span& &span class=&n&&r&/span&&span class=&o&&.&/span&&span class=&n&&zrange&/span&&span class=&p&&(&/span&&span class=&s&&&search_rank_zlist&&/span&&span class=&p&&,&/span& &span class=&o&&-&/span&&span class=&mi&&10&/span&&span class=&p&&,&/span& &span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&,&/span& &span class=&n&&withscores&/span&&span class=&o&&=&/span&&span class=&bp&&True&/span&&span class=&p&&)&/span& &span class=&c&&# TOP 10 rank&/span&
&span class=&k&&print&/span& &span class=&n&&time&/span&&span class=&o&&.&/span&&span class=&n&&time&/span&&span class=&p&&()&/span& &span class=&o&&-&/span& &span class=&n&&begin2&/span& &span class=&c&&# 0.7s ~ 1.2s if KEY_LEN= 3 ~0.4s if KEY_LEN = 10000&/span&
&span class=&c&&#memory 800M&/span&
&span class=&k&&return&/span& &span class=&n&&res&/span& &span class=&c&&#这里使用读写分离每一秒钟更新一次，并且获得最新的数据，作为缓存，接下来一秒钟的所有访问都用这个结果&/span&
&span class=&k&&if&/span& &span class=&n&&__name__&/span& &span class=&o&&==&/span& &span class=&s&&&__main__&&/span&&span class=&p&&:&/span&
&span class=&n&&insert_test_data&/span&&span class=&p&&()&/span&
&span class=&k&&print&/span& &span class=&s&&&test_insert_begin&&/span&
&span class=&n&&insert_new_data&/span&&span class=&p&&()&/span&
&/code&&/pre&&/div&&p&其他问题:&/p&&p&1.如果是统计24小时之内的搜索量的排名（一般一秒之内的排名波动过大，产品意义不大），可以考虑，进去一个1s出去一个1s的原则，记录2天之内每一秒的操作，然后加入现在这一秒然后减去昨天这一秒（对于redis就是zincrby负数，相当于消耗时间变成了1.5倍～2倍吧）。&/p&&p&2. 1s中之内真的有100万次搜索(估计不是搜索而是其他什么奇葩的业务)，而且只统计1秒钟，那就使用topK算法，时间复杂度NlogK，估计非常勉强。&/p&&p&3. 1秒钟真的有几百万次，而且统计1天（几千亿每天，不建议几千亿请求全部落地存储），这个估计只能做抽样，抽1/100变成几万个。。。具体误差可以用二项分布计算一下，详情参照各大统计课程。&/p&&p&4. 在3的基础上，需要统计任意时间段（好几天）的数据，做好抽样，然后配合各大专业分析型数据库，抽样会对UV类别的计算产生影响，可以考虑再弄个hyperloglog算法，统计每一小时的情况，然后通过hyperloglog合并成多天的UV估计。。。&/p&
先确定一下量级：数据量百万级别指的是系统累计一共有几百万的搜索词还是一秒钟有几百万次搜索（貌似一秒钟不应该几百万次搜索）？默认第一种，做出以下假定，如果一秒钟几万次搜索（一天几十亿次, 百度搜索的pv量级）并且这一秒钟的搜索落在1万个左右的独…
&p&谢邀&/p&&p&首先你没贴出来exch实现是啥，exch的位置应该是对a[j]和a[j-h]进行交换，跟i没有任何关系，如果是对a[i]和a[j]交换，我的测试是失败的，不能正常排序，所以最好先检查下执行是否成功&/p&&p&其次，如果你每次i+=h，则实际上每轮只是对i为h的倍数的位置进行一次间隔的插入排序，无法实现快速减少逆序数的效果，所以怀疑你时间统计的代码（你也没贴出来），而我的测试，是你上面Shell的比你改的Shell1快300倍，用15w个double，如果是500w那Shell1跑个几天都出不来的&/p&&p&代码最好贴全了，很多时候是你用错误的测试方式得到了错误的结果&/p&&p&最后反对一下上面陈硕的回答，第一，不管题主是什么动机研究shell排序，他问的只是这方面的技术问题，就算要提醒学习方式也可以在回答之后进行，第二，希尔排序在大规模数据下速度还是很快的，虽然大体上比不上快排，但复杂度是亚二次的（序列选好的话可以到O(N^1.167)），而且空间复杂度O(1)，是一种实用排序法，第三，内部排序而言，归并由于要消耗O(N)空间，反倒是不太常用，虽然Python之类的sort实现用到&/p&
谢邀首先你没贴出来exch实现是啥，exch的位置应该是对a[j]和a[j-h]进行交换，跟i没有任何关系，如果是对a[i]和a[j]交换，我的测试是失败的，不能正常排序，所以最好先检查下执行是否成功其次，如果你每次i+=h，则实际上每轮只是对i为h的倍数的位置进行一次…
已有帐号？
无法登录？
社交帐号登录}