Category Archives: C && C++

算法技术手册 – 排序 – 如何选择排序算法

实际上，没有绝对优秀的、应该始终采用的排序算法。

书上给出了一些选择不同排序算法的理由，写的非常好，抄录一下。

元素很少：插入排序
几乎有序：插入排序
关注最差情况：堆排序（牢记：堆排序的最差时间复杂度依然是O(nlogn)）
平均较好：快速排序
元素从密集范围取出：桶排序
代码量小：插入排序

书上也在不同应用环境：字符串、浮点、几乎有序等情况下进行了测试，有兴趣的可以去翻阅。[......]

算法技术手册 – 排序 – 桶排序/哈希排序/散列排序

1 Reply

在前面的计数排序中，我们已经领略到了如何用空间换时间的方法，找到一种线性时间复杂度O(N)的排序算法。

计数排序的缺点也是非常明显的：一旦数据范围[0,k)，中的k]相对于数据量N非常稀疏，计数排序的空间会非常大、时间消耗也会增大非常大。当然主要还是空间问题。

个人认为：桶排序 = 哈希排序 = 散列排序，基本思想是一样的。

于是桶排序/哈希排序应运而生，假设值域范围还是k，我们不去创建k个buckets，而是创建m个木桶，让N个元素通过哈系函数映射到这k个桶即可。这里还有一个[......]

算法技术手册 – 排序 – 计数排序

如果已知被排序的n个元素，值范围固定在在 "[0,k)"内]，那么计数排序是最好的选择，它具有线性复杂度。

这个约束有些过强，有些时候，可以将不满足这个条件的转化一下：
比如 [-k, k)映射]到[0, 2k)等]。
再比如1/p的小树映射到p k-p等等。

下面上算法，主要走两遍：
首先建立k个桶
(1)扫描n个元素，增加对应桶中的计数
(2)从小到大扫描k个桶，计数非零则减一，然后顺序、依次输出。

源代码：
#include <stdio.h>[......]

推荐开源的INI文件解析器SimpleINI(c++)

在Python中，INI解析这种问题交给ConfigParser就行了，非常简单，但是C++显然没有原生的类库解决问题。
Windows下的ini API不是可移植的，所以无视它。

推荐一个非常好用的，跨平台的INI解析器：SimpleINI，支持section，读、写、各种value，遍历等。

网址：http://code.jellycan.com/simpleini/

旧代码废弃了，已经托管到github上：https://github.com/brofield/simp[......]

学习Xapian(3) – 同义词的查询拓展

Xapian支持同义词的查询拓展。
按照同义词进行拓展算是查询拓展最基本的一种方式。
比如“汽车展览”和“车展”是同义词，我们搜索汽车展览的时候，也会把“车展”的结果返回。
很多人认为这个就是拼写校正，但实际它比拼写校正稍微高级点，特别是放在Xapian的语境下，毕竟拼写校正是基于编辑距离而不是语义的。

1、在DB写入同义词组
创建同义词组的API很简明。
WritableDatabase::add_synonym(term, synonym)
这一对同义词是有方向的，term[......]