阅读全文…LRU(Least recently used，最近最少使用)算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
Stack Pub
欢迎来到堆栈酒馆。
-
-
哈希表
哈希表(hash table)也叫散列表，是根据关键字(Key value)直接进行访问的数据结构。也就是说，它通过把关键字映射到表中位置来进行访问的。这个映射函数叫做哈希函数或者散列函数，存放记录的空间叫做哈希表或者散列表。
哈希表的装填因子 $\alpha$ 反应着哈希表装满的程度, $\alpha = 填入表中的记录个数 / 哈希表长度$, $\alpha$ 越小,表明哈希表中存储的记录越少,发生冲突的可能性越小,哈希表的平均查找长度取决于装填因子,而不是哈希表中的记录个数。
阅读全文… -
排序
阅读全文…方法 最好 最坏 平均 空间复杂度 稳定性 冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定 快速排序 $O(n\log_{2}n)$ $O(n^2)$ $O(n\log_{2}n)$ $O(n\log_{2}n)$ 不稳定 直接插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定 希尔排序 $O(n^{1.3})$ $O(1)$ 不稳定 简单选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定 堆排序 $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(1)$ 不稳定 归并排序 $O(n\log_{2}n)$ $O(n\log_2{2}n)$ $O(n\log_{2}n)$ $O(n)$ 稳定 基数排序 $O(d(r+n))$ $O(d(r+n))$ $O(d(r+n))$ $O(r)$ 稳定 -
线性查找算法
查找是在一些(有序/无序)的数据元素中通过一定的方法找出与给定关键字相同的数据元素。
阅读全文… -
二叉树
树(Tree)是由$n(n>=0)$个结点组成的一个具有层次关系的非线性有限集合，树中的每个元素被称为树的节点，每个节点有若干个指针指向的后继结点(子结点)。树中节点的子树数目称为节点的度(degree)。树中各结点度的最大值称为树的度，通常称为几次树。度为0的结点称为叶子结点。
阅读全文… -
栈与队列
-
C++ Primer(六) 模板与泛型编程
面向对象编程和泛型编程都能处理在编写程序时不知道类型的情况。OOP能处理类型在程序运行之前都未知的情况；而泛型编程中，在编译时就可以获知类型。
阅读全文… -
C++ Primer(五) 面向对象程序设计
OOP：概述
面向对象程序设计（object-oriented programming）的核心思想是数据抽象、继承和动态绑定。
继承（inheritance）：通过继承联系在一起的类构成一种层次关系。通常在层次关系的根部有一个基类（base class）。其他类直接或者间接从基类继承而来，这些继承得到的类成为派生类（derived class）。基类负责定义在层次关系中所有类共同拥有的成员，而每个派生类定义各自特有的成员。
阅读全文…