1. 快速排序
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];/*用字表的第一个记录作为枢轴*/
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/*将比第一个小的移到低端*/
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];
/*将比第一个大的移到高端*/
}
a[first] = key;/*枢轴记录到位*/
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}2 . 一个排序数组中所有数字出现2次，其中一个数字只出现1次，找出这个数字？
只需要将所有数字做一遍异或就能得到该数字。
int getonenum(int a[],int size)
{
int resualt=0;
for(int i=0;i<size;i++)
{
resualt^=a[i];
}
return resualt;
}3 . 二叉树
二叉树的数组表示，对于根节点i，左子树为2i，右子树为2i+1.有子树存相应值，没有就空着。
public class ArrayTree
{
private Object array[];
private int nodenum;
public ArrayTree ()
{
array=new Object[20];
nodenum=20;
for(int i=1;i<nodenum;i++)
{
array[i]=null;
}
}
public Object root() //返回根结点
{
return array[1];
}
public Object left(int i) //返回左孩子
{
return array[i*2];
}
public Object right(int i)//返回右孩子
{
return array[i*2+1];
}
} 求第k层叶子个数的方法,对于数组存储的，直接循环查看2^(k-1)-(2^k-1)之间的元素，是否有值统计就能得出个数。
对于非数组存储的，使用递归方式：
int GetBTreeKthLevelNodesTotal( BTreeNode_t *pRoot, int KthLevel){
if( pRoot == NULL || KthLevel <= 0 )
return 0;
if( pRoot != NULL && KthLevel == 1 )
return 1;
return (GetBTreeKthLevelNodesTotal( pRoot->m_pLeft, KthLevel-1) + GetBTreeKthLevelNodesTotal( pRoot->m_pRight, KthLevel - 1 ) );
}非递归方式，可以借助队列实现
int GetKthLevelNodesTotal( BTreeNode_t *pRoot, unsigned int KthLevel ){
if( pRoot == NULL )
return 0;
queue <BTreeNode_t *> que;
que.push( pRoot );
int curLevelNodesTotal = 0;
int curLevel = 0;
while( !que.empty() ){
++curLevel;//当前层数
curLevelNodesTotal = que.size();
if( curLevel == KthLevel )//如果层数等于给定层数
break;
int cntNode = 0;
while( cntNode < curLevelNodesTotal){//将下一层节点入队
++cntNode;
pRoot = que.front();
que.pop();
if( pRoot->m_pLeft != NULL )
que.push(pRoot->m_pLeft);
if( pRoot->m_pRight != NULL )
que.push( pRoot->m_pRight);
}
}
while ( !que.empty() )
que.pop();
if( curLevel == KthLevel )
return curLevelNodesTotal;
return 0; //如果KthLevel大于树的深度
}4 . 不用加减乘除求两个数的和
先异或，再与运算。
int AddWithoutArithmetic(int num1, int num2)
{
if(num2 == 0)
return num1;
int sum = num1 ^ num2; //异或运算
int carry = (num1 & num2) << 1; //对0加0、0加1、1加0而言，都不会产生进位，只有1加1时，会向前产生一个进位。因此两个数先做位与运算，然后再向左移动一位。
return AddWithoutArithmetic(sum, carry);
} 5 . 一个公司内所有人的年龄排序
，时间复杂度为O(n)，空间复杂度为O(1)
桶排序
6 .银行家算法
算法思想：
1、假分配检测：Request < Need
Request < Available
2、安全序列检测算法
实例列举：
某系统有R1，R2，R3共3中资源，在T0时刻P0，P1，P2，P3和P4这5个进程对资源的占用和需求情况如下表1，此时系统的可用资源向量为(3,3,2)。试问：
1、T0时刻系统是否存在安全序列？
2、P1请求资源：P1发出请求向量Request（1,0,2），系统是否接受该请求？请使用银行家算法检查
3、P4请求资源：P4发出请求向量Request（3,3,0），系统按银行家算法检查.
4、P0请求资源：P0发出请求向量Request（0,2,0），系统按银行家算法检查.
表1 T0时刻的资源分配表
| 进程ID | MAX | Allocation | Need | Available |
|---|---|---|---|---|
| P0 | 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2 |
| P1 | 3 2 2 | 2 0 0 | 1 2 2 | |
| P2 | 9 0 2 | 3 0 2 | 6 0 0 | |
| P3 | 2 2 2 | 2 1 1 | 0 1 1 | |
| P4 | 2 2 2 | 0 0 2 | 4 3 1 |
an：
1、T0时刻系统是否存在安全序列？
Available > Need1 —-> 可用资源分配给P1，直到P1进程执行完成，然后Available = Available + Allocation1 = （5,3,2）
Available > Need3 -----> 可用资源分配给P3，直到P3进程执行完成，然后Available = Available + Allocation3 = （7,4,3）
Available> Need4…..
得到安全序列为：P1，P3，P4，P2，P0
2、P1请求资源：P1发出请求向量Request（1,0,2），系统是否接受该请求？请使用银行家算法检查
第一步（假分配检查）：把Request分配给P1，必须满足Request要小于Available，Request要小于Need。
Request（1,0,2）< Available（3,3,2）
Request（1,0,2）< Need（1,2,2）
因为满足第一步检查，进入第二层检查（安全序列检查）。
第二步（安全序列检查）：建立安全性检查表
| 进程ID | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| P1 | 2 3 0 | 0 2 0 | 3 0 2 |
如果 Work > Need ,那么执行Work+Allocation，得到：
| 进程ID | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| P1 | 2 3 0 | 0 2 0 | 3 0 2 | 5 3 2 | true |
| 5 3 2 |
找到Need < Work的进程，如果没有找到这样的进程而进程集合没有执行，则算法返回，得到不存在安全序列结果，否则继续执行该算法。
这里我们找到了P3进程。修改安全序列检查表：
| 进程ID | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| P1 | 2 3 0 | 0 2 0 | 3 0 2 | 5 3 2 | true |
| P3 | 5 3 2 | 0 1 1 | 2 1 1 | 7 4 3 | true |
| 7 4 3 |
这样一直执行到所有的进程到完成，以完成该安全序列检查表：
| 进程ID | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| P1 | 2 3 0 | 0 2 0 | 3 0 2 | 5 3 2 | true |
| P3 | 5 3 2 | 0 1 1 | 2 1 1 | 7 4 3 | true |
| P4 | 7 4 3 | 4 3 1 | 0 0 2 | 7 4 5 | true |
| P0 | 7 4 5 | 7 4 3 | 0 1 0 | 7 5 5 | true |
| P2 | 7 5 5 | 6 0 0 | 3 0 2 | 10 5 7 | true |
这样就找到了整个安全序列为：P1，P3，P4，P0，P2
7 . B+树和B-树
B-树是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
如：（M=3）
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果
命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为
空，或已经是叶子结点；
B-树的特性：
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少
利用率，其最底搜索性能为：
其中，M为设定的非叶子结点最多子树个数，N为关键字总数；
所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占
M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；
B+树
B+树是B-树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树
（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；
如：（M=3）
B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在
非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
B+的特性：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；
8 . 单链表是否有环并如何找到环入口
1、如何判断一个链表是不是有环？
2、如果链表为存在环，如果找到环的入口点？
一般通用的做法就是弄两个指针，一个走得快一点，一个走得慢一点。一般是弄一个走一步，一个走两步。这样如果他们相遇，则说明有环。那么在有环的基础上，怎么找到这个环的入口呢?
走一步的指针叫slow，走两步的叫fast。
相遇的时候，slow共移动了s步，fast共移动了2s步，这个是显而易见的。
定义a如下： 链表头移动a步到达入口点。
定义x如下： 入口点移动x步到达相遇点。
定义r如下： 从环中的某一点移动r步，又到达的这一点，也就是转了一圈的意思。
定义t如下： 从相遇点移动到入口点的移动步数
定义L如下： 从链表头移动L步，又到达了相遇点。也就是遍历完链表之后，通过最后一个节点的指针，又移动到了链表中的某一点。
其中Ｌ ＝ a + r = a + x + t
那么slow和fast相遇了，fast必然比slow多走了n个圈，也就是 n*r 步，那么
s = a + x
2s = s + n*r ， 可得 s = n*r
将s=a+x，带入s =n*r，可得 a+x = n*r, 也就是 a+x = (n-1)*r + r
从表头移动到入口点，再从入口点移动到入口点，也就是移动了整个链表的距离，即是 L = a + r , 所以r = L - a
所以 a+x = (n-1)*r + L - a , 于是 a = (n-1)*r + L - a - x = (n-1)*r + t
也就是说，从表头到入口点的距离，等于从相遇点继续遍历又到表头的距离。
所以，从表头设立一个指针，从相遇点设立一个指针，两个同时移动，必然能够在入口点相遇，这样，就求出了相遇点。
代码如下：
typedef struct node{
int elem;
struct node * next;
}Node, *NodeList;
//寻找环的入口点
NodeList FindLoopPort(NodeList head)
{
NodeList slow=head,fast=head;
//得到相遇点
while(fast && fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
break;
}
if(fast==NULL||fast->next==NULL)
return NULL;
//slow指向开头，fast在相遇点
//得到入口点
slow=head;
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}9 .如何两个栈实现一个队列
最后一种方法，s2永远都不会倒回s1。
在出队时，判断s2为空, 将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队, 之后不需要将s2倒回s1。
举个例子：s1从栈底到栈顶依次为1、2、3，s2为空，此时做出队操作：把s1倒入s2，则s2从栈底到栈顶依次为3、2、1，将栈顶的1弹出，之后不用把s2倒回s1。之后，如果入队两个元素，如4、5，则将其压入s1；如果此时出队一个元素，由于s2不为空，则直接弹出栈顶的2；再出队，由于s2还不为空，则直接弹出栈顶的3；再次出队，由于s2为空了，将s1的元素（依次为5、4）倒入s2，再弹出栈顶的4，再出队，由于s2又不为空了，直接弹出5。一切正常。
10 . 倒排索引
倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。
倒排文件（倒排索引），索引对象是文档或者文档集合中的单词等，用来存储这些单词在一个文档或者一组文档中的存储位置，是对文档或者文档集合的一种最常用的索引机制。
搜索引擎的关键步骤就是建立倒排索引，倒排索引一般表示为一个关键词，然后是它的频度（出现的次数），位置（出现在哪一篇文章或网页中，及有关的日期，作者等信息），它相当于为互联网上几千亿页网页做了一个索引，好比一本书的目录、标签一般。读者想看哪一个主题相关的章节，直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页，一页一页的查找。
11.Trie树
Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。
Trie一词来自retrieve，发音为/tri:/ “tree”，也有人读为/traɪ/ “try”。
Trie树可以利用字符串的公共前缀来节约存储空间。如下图所示，该trie树用10个节点保存了6个字符串tea，ten，to，in，inn，int： 
在该trie树中，字符串in，inn和int的公共前缀是“in”，因此可以只存储一份“in”以节省空间。当然，如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存，这也是trie树的一个缺点。
Trie树的基本性质可以归纳为：
（1）根节点不包含字符，除根节点意外每个节点只包含一个字符。
（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。