位图法总结

缘起

位图法是桶排序思想的延伸. 比如我们想知道 200以内的正整数 某个元素， 例如163，是否存在, 我们需要

int flag[200], flag[163]=1表示存在, 0表示不存在. 即需要 200*4=800字节的桶才能维护这样的状态. 或者至少

bool flag[200], 即 200字节维护这一状态. 但是如果使用位图思想——它精简到使用一个bit来记录某个正整数的状态. 例如163, 163/8=20…3 即第20字节的第3个比特的状态就可以刻画163. 所以使用位图思想的话, 只需要200/8=25字节就足够了.

位图思想使用1个比特位表示一个状态，算法的精简性适用于海量数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

Read More

堆排序

缘起

堆排序又叫做优先队列. 在c++ 的STL中的模板类priority_queue\以及java中的java.util.PriorityQueue 无疑都给出了堆的实现. 这个算法属于内排序中最快、性能最稳定（快排虽然也是O(nlogn)但是最坏亦可以堕落到O（n^2），而堆排稳定在O（nlogn））的一类算法, 但是因为涉及到非相邻元素之间的交换, 所以堆排不是稳定的排序。 但是堆排序是就地算法.

Read More

基数排序

缘起

【1】和【2】分别介绍了非比较排序的桶排序和计数排序两种算法. 两种算法的缺点无疑就是空间复杂度太高——万一空间卡的比较死，然后参与排序的数值分布比较稀疏的话, 时间复杂度和空间复杂度都会较高. 而基数排序结合了桶排序的特点，但是空间复杂度不高. 对比桶排序，基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作，而桶排序在桶相对较少的情况下，桶内多个数据必须进行基于比较操作的排序。因此，在实际应用中，基数排序的应用范围更加广泛。

Read More

CBA理论, 为什么基于比较的排序方法的性能极限是O(nlogn)

缘起

排序是计算机科学中的基础算法, 很多算法，譬如图算法等都基于排序算法. 所以弄清楚排序算法的性能极限是很重要的. 很多排序——快排、堆排、归并、胜者树等基于比较的排序算法的性能都是O(nlogn). 其实

CBA（comparison-based-algorithm）理论： 任何基于比较的排序算法的性能天花板就是O(nlogn)

Read More

非比较排序之计数排序

缘起

【1】中讲解了非比较排序中的一种——桶排序. 这里介绍非比较排序的第二种——计数排序， 非比较排序的性能都是可以到达O(n)这种线性性能的. 因为都是使用hash进行空间换时间. 注意, 正因为需要空间换时间, 所以基于hash的排序算法需要明确参与排序的数值有一定的范围. 范围越大, 越消耗空间.

Read More

非选择排序之桶排序

缘起

之前介绍的无论是选择排序还是冒泡还是插入还是快排还是堆排序, 都是基于CBA理论（comparison-based-algorithm）， 对应的结果集就是一棵树, 所以CBA最优时间复杂度就是 nlogn. 但是这里要讲的桶排序不属于比较排序,所以他的排序性能可以飙升到O(n).

Read More