实现Quicksort时,您需要做的一件事就是选择一个数据透视表.但是当我看下面的伪代码时,我不知道应该如何选择枢轴.列表的第一个要素？别的什么？
function quicksort(array)
var list less, greater
if length(array) ? 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ? pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))
有人可以帮助我掌握选择枢轴的概念,以及不同的场景是否需要不同的策略.
所以,由于一些奇怪的原因,我最终得到一个100GB的未分类日志文件(实际上它是部分排序的),而我试图应用的算法需要排序数据.日志文件中的一行看起来像这样
data <date> data data more data
我可以在工作站上访问C#4.0和大约4 GB的RAM.我认为合并 - 某种类型在这里最好,但是我自己实现这些算法还不够 - 我想问一下我是否可以采取某种捷径.
顺便说一句,解析日期字符串DateTime.Parse()非常慢,占用了大量的CPU时间 - chugging -rate几乎是10 MB /秒.有比以下更快的方式吗？
public static DateTime Parse(string data)
{
int year, month, day;
int.TryParse(data.Substring(0, 4), out year);
int.TryParse(data.Substring(5, 2), out month);
int.TryParse(data.Substring(8, 2), out day);
return new DateTime(year, month, day);
}
我写道,为了加快速度DateTime.Parse(),它确实运行良好,但仍然需要大量的循环.
请注意,对于当前的日志文件,我也对小时,分钟和秒感兴趣.我知道我可以使用格式提供DateTime.Parse(),但这似乎并没有加快它的速度.
我正在寻找正确方向的推动,提前谢谢.
编辑:有些人建议我使用字符串比较来比较日期.这适用于排序阶段,但我确实需要解析算法的日期.我仍然不知道如何在4GB的免费RAM上对100GB文件进行排序,而无需手动操作.
编辑2:嗯,多亏了我使用windows排序的一些建议,我发现Linux上有类似的工具.基本上你叫sort,它会为你修复一切.正如我们所说,它正在做一些事情,我希望它能尽快结束.我正在使用的命令是
sort -k 2b 2008.log > 2008.sorted.log
-k指定我要对第二行进行排序,第二行是通常YYYY-MM-DD hh:mm:ss.msek格式的日期时间字符串.我必须承认,man-pages缺乏解释所有选项,但我通过运行找到了很多例子info coreutils …
我在Adobe采访中被问到这个问题:
我们有一个整数数组,按升序排序.我们还有3个整数A,B和C.我们需要申请数组中的A*x*x + B*x + C每个元素x并返回相应的排序数组.
示例I给出了:
Input array = -1 0 1 2 3 4
A = -1, B = 2, C = -1`
将公式应用于每个元素的-4 -1 0 -1 -4 -9
结果=所以预期结果= -9 -4 -4 -1 -1 0(已排序)
我最好的解决方案是应用配方并对其进行分类以产生O(nlogn)解决方案.我无法做得更好.
任何改进它的指导都是有帮助的.
我正在排序整数键的数组.
stdlib.h qsort ;
这很慢,现在我的函数在每次执行的排序上花费0.6秒,stdlib.h qsort是1.0s; 这与std :: sort具有相同的性能
蒂姆索特 ;
我试过这个:https://github.com/swenson/sort和这个:http://code.google.com/p/timsort/source/browse/trunk/timSort.c？specs = snn17&r = 17 ; 两者都明显慢于stdlib qsort
到目前为止,他们对快速排序和插入排序的组合对我的数据来说是最快的; 我尝试了各种设置和pivot作为中间元素(不是3的中位数)和插入排序从28个元素子数组开始(默认情况下不是8)提供最佳性能
贝壳排序 ;
本文中的差距很简单:http://en.wikipedia.org/wiki/Shellsort ; 它很不错,虽然比stdlib qsort慢
我的想法是qsort做了很多交换和废弃(即反向)排序的子序列,所以应该有一些方法通过利用数据的结构来改进它,不幸的是我的所有尝试到目前为止都失败了.
如果你很好奇那是什么类型的数据,那些是在已经在前面板上排序的各种板上评估的扑克牌组(这是排序后的子序列来自哪里).
该功能在C.我使用Visual Studio 2010.任何想法？
示例数据:http://pastebin.com/kKUdnU3N
示例完整执行(1176种):https://dl.dropbox.com/u/86311885/out.zip
我有一个字符串列表,已按特定的比较函数排序.
现在我必须使用不同的比较函数重新排序此列表.
这种新的比较函数在比较某些特殊字符(例如变形金刚)时表现略有不同.在大多数情况下,元件必须仅移动一个或两个槽以到达正确的位置.
哪种排序算法最适合根据运行时执行速度对这个几乎完全排序的列表进行重新排序？
例如,
foo1
foo2
foo10
foo100
而不是
foo1
foo10
foo100
foo2
更新:对自己编码排序不感兴趣(虽然这本身就很有趣),但让数据库为我做排序.
如果这是一个愚蠢的问题,请原谅我......但我想回到我的Comp.科学.类和我清楚地记得在几种排序算法和相应的"大O"符号上学习/被测验.
但是,在课堂之外,我从来没有真正编写代码来进行排序.
当我从数据库获得结果时,我使用'Order By'.否则,我使用实现排序的集合类.我已经实现了IComparable以允许排序; 但我从来没有超越过那个.
对于那些没有实现语言/框架的人来说,排序总是只是一种学术追求吗？或者只是在现代硬件上运行的现代语言使它成为一个需要担心的微不足道的细节？
最后,当我在List(Of String)上调用.Sort时,例如,在引擎盖下使用了什么类型的算法？
我有一个这样的数组:
1,2,3,5,6,4它是99%排序和40K元素.
我可以把它们放在一个数组,列表,链表中......
但我不知道排序它们的最快方法!
所以我猜它是因为它只是比较 A[k] 和 A[k-1]，并在一次扫描中实现，但它仍然不清楚。有人可以更好地解释一下吗？谢谢
给定一个整数列表,我怎样才能最好地找到一个不在列表中的整数？
列表可能非常大,整数可能很大(即BigIntegers,而不仅仅是32位整数).
如果它有任何不同,列表"可能"排序,即99%的时间它将被排序,但我不能依赖总是被排序.
编辑 -
为了澄清,给出列表{0,1,3,4,7},可接受的解决方案的例子将是-2,2,8和10012,但我更愿意找到最小的,非负解决方案(即2)如果有一个算法可以找到它而无需对整个列表进行排序.
我正在处理文件中的整数列表。我必须使用排序算法按降序对它们进行分类。我熟悉一些排序算法的运行时间，并且我知道它们的使用是视情况而定的。所以我的问题是：对于已经 90% 排序的任何大小的列表，最快的排序算法是什么？（在我的文件中，我有 10.000 个条目，但其中 9.500 个已经排序）。
谢谢，
如果你有一个字符串数组,那么按升序排序这个数组的最快方法是什么？