我真的很喜欢研究算法和优化代码（我尽量不要过早地做）因为当现在需要5分钟运行的东西在2分钟内运行时感觉非常酷 . 我对搜索算法特别感兴趣，因为当你必须在表中搜索匹配的子字符串或条目时，它是如此频繁 .
我正在考虑比较排序的下限，并考虑如何比较排序可以通过猜测答案是什么来跳过一些比较，然后整行比较可能会消失，高度降低1.（例如，如果一个算法可以猜测bcd在一起，那么排序a，b，c，d，e，f那么你实际上只是排序a，bcd，e，f）猜测必须是聪明的，有效的猜测让它值得，加上需要有相当不错的击球率 .
与搜索相同，如果智能搜索可以首先猜测项目可能在哪里，并且仅搜索前5个猜测区域 . 如果所有5个猜测都是错误的，那么它可能会返回一个错误的答案并且永远不会找到该项目，但如果它具有足够好的正确比率，那么它可能与它相关 . 它可能比创建二进制搜索树然后进行log（n）搜索更快 .
无论如何，我相信任何理解这个主题的人都会意识到这主要是猜测/幻想而没有实质内容所以我正在寻求帮助，以便在学习没有100的算法方面采取措施％正确返回，特别是在搜索/排序区域，但更快并且应用这些算法 .
我用谷歌搜索，点击维基百科上的随机链接试图找到这个，但没有令人满意的结果 . 我应该阅读什么/我应该去哪里开始学习这个？
我想我应该提到我对大多数“标准”算法和数据结构感到满意，如快速排序，合并排序，气泡，基数，计数等，以及哈希，自 balancer 树等 .
3 回答
我认为要取得很大成就，你必须为你的“几乎排序”定义一些标准 . 例如，如果在正确位置的N个点内有一个元素就足够了，你可以做一些像Quicksort这样的事情，但是当一个分区到达N个元素时停止 . 请注意，执行此操作已经很常见，并使用插入排序完成作业 . 但是，除非N非常大，否则你可能不会从中获得太多 .
就搜索而言，你're probably looking for what'通常称为插值搜索 . 而不是总是猜测范围的中间，你使用插值来猜测你正在寻找以'b'开头的字符串的项目的可能位置，你开始通过集合的1/13而不是一半通过 .
如果集合中的项目分布极不均匀，后者可能效果不佳，但假设分布合理均匀，则会产生非常好的结果（大约为O（log log N）而不是O（log N）你得到二分搜索） . 但是，它确实依赖于均匀分布，并且具有一种键值类型，您可以计算至少与"distance"类似的东西，而不仅仅是"less than"或"greater than"比较 . 在实践中，它通常可以很好地工作（并且它通常在前面是非常明显的情况） .
近似排序不会比正确排序快得多 .
好的，所以我们还没有真正定义“近似”，但任何合理的定义都意味着结果数据的反转总数相当少（反转是一对错误的方法）彼此） .
但是，几乎排序的数据可以非常快速地正确排序 . 例如，插入排序是O（n d），其中n是元素的数量，d是反转的数量 .
因此，如果您可以“快速”对数据进行“快速”排序，那么您可以“快速”对其进行正确排序 . 几乎排序和正确排序之间的区别只是“有点” .
有一次，我使用每次运行最大数量的“插入”的插入排序，以便大致维持一段时间的排序（保证特定计算时间上限比精确度更重要） . 但我同意史蒂夫杰索普的观点：一般来说，没有理由贬低 . 还有像TimSort这样的算法，旨在识别和利用“简单案例” .