Shen Jianan's blog

Freedom as Autonomy

应用场景 基数统计(Cardinality Counting)指计算一个数据集中不同元素的数量，在很多场景都需要这样的功能：电商场景中的独立用户(UV)数量统计、数据库中快速计算字段取值数量以优化query、计算与某个站点相关的不同链接数量等。

再探排序 记得之前写过一篇关于快排的博客，当时只是写了一个快排的代码片段，加上简单的优化意见——当递归到一定规模的序列时使用插排提升效率、随机选取比较的元。那篇博客是在准备面试时看到网上一些资料而写的简单的笔记。 最近在重新读《数据结构与算法分析》，这本书是大二时数据结构课的教材。记得当初上课没有用心学习，最后的成绩也算是勉勉强强八十几分。到现在，对于排序也就记得大体的思想，真正上手写代码却是漏洞百出。现在重新回顾，得到了很多新的感悟，原来像团团迷雾的算法细节也终于清晰起来。本篇博客会对插入排序、希尔排序、快速排序、归并排序的读书体会与收获进行记录。

二叉树是很重要的数据结构，今次的任务是复习一下搜索二叉树和红黑树~主要对应《算法导论》中的《二叉搜索树》和《红黑树》两章。这里的搜索二叉树不是B树，所以插入操作时不需要进行专门的旋转操作。

任何基于决策树的比较排序在最坏情况下都要经过$\Omega(nlgn)$次比较。因此，任何已知的比较排序最多在常数因子上优于归并排序和堆排序。

快速排序最坏情况下的时间复杂度是$\Theta(n^2)$，但是它的期望时间复杂度是$\Theta(nlogn)$，而且隐含的常数因子非常小。 今天的文章复习一下快排的原理和尝试着自己实现一下代码。