Using指令
using指令概要A using-directive is a block-declaration（{/block/}）
作用
Using-directives are allowed only in namespace scope and in block scope. From the point of view of unqualified name lookup of any name after a using-directive and until the end of the scope in which it appears, every name from namespace-name is visible as if it were declared in the nearest enclosing namespace which contains both the using-directive and namespace-name.
using指令与声明区域Using-directive does not add any names to the declara ...
Using声明
Using 声明概要
Introduces a name that is defined elsewhere into the declarative region where this using-declaration appears.
作用Using-declarations can be used to introduce namespace members into other namespaces and block scopes, or to introduce base class members into derived class definitions.
using 声明是实实在在的引入了这个namespace member，这个声明是可以加入name lookup的查找集的，这点与using指令是不同的。
形式
A using-declaration with more than one using-declarator is equivalent to a corresponding sequence of using-declarations with o ...
swap与copy(and move) assignment
std::swap构造拷贝（和移动）赋值运算符的坑
我们来看一下循环队列头文件中：SQ.h有以下代码（已注释）：1234567template<typename T>Queue<T>& Queue<T>::operator=(const Queue<T> &rhs){ Queue copy=rhs; std::swap(*this,copy); return *this;}上面这个拷贝赋值运算符重载是错误的，我们首先要清楚swap是以怎样的形式工作的：swap(T &a,T &b) {T temp(move(a));a=move(b);b=move(temp);}所以std::swap需要移动构造函数和移动赋值运算符，而拷贝构造函数和拷贝赋值运算符阻止了编译器自动合成它们（假设我们并没有设置自定义的），swap第一个构造尚且可以用拷贝构造代替移动构造，但是下面的赋值运算符找不到移动赋值运算符，就会不断调用拷贝赋值运算符，因此它会一直卡死在这里，我们可 ...
AVL
AVL-TreeAVL树简介一棵AVL树有如下必要条件：
它必须是二叉查找树。
每个节点的左子树和右子树的高度差至多为1
AVL树的优势AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn），这得益于它时刻维护着二叉树的平衡。如果我们需要查找的集合本身没有顺序，在频繁查找的同时也经常的插入和删除，AVL树是不错的选择。不平衡的二叉查找树在查找时的效率是很低的。AVL树的相关概念平衡因子（BF）将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)最小不平衡树距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树。结点类型12345678910template<typename T>struct AVL_Node { T data; int height; AVL_Node<T>* lchild, * rchild; //构造函数 AVL_Node():lchild(nullptr),rchild(nullptr),height(0){} AVL_Node(T d, ...
KMP
KMP算法KMP由来KMP发展自朴素模式匹配算法，但过于低效，难以处理多个0与1重复组成的字符串，因此三位大牛：D.E.knuth,J.H.Morris和V.R.Pratt发表一种新的模式匹配算法，性能远超朴素算法。取三人名字首字母组成的算法就称为KMP算法。
朴素模式匹配算法在学习KMP算法之前先了解下朴素匹配算法
图例分析令文本串S=”goodgoogle”，模式串T=”google”则步骤如下：前三个都匹配正常，第四个匹配失败。第一位匹配失败。显然，第二、三、四位全部匹配失败,而第五位匹配成功，从第五位开始的6个字母全匹配。
算法分析朴素模式匹配算法就是文本串每个字符作为模式串开头来与子串匹配，这样对文本串做一个大循环，而模式串做T的长度的小循环，直到全部匹配。
实现代码123456789101112131415161718192021int Violent_Match(String S,String T){ int i=0,j=0; while(i<S.length&&j<T.length) { if(S[i]==T[ ...
十大排序——希尔排序
希尔排序基本思想希尔排序本质也是插入排序，又称缩小增量排序但效率打破了O(n^2)。希尔排序是将待排序序列分成若干个小序列，并对这些小序列进行直接插入排序，待整个序列都保持“基本有序”时再对整体进行一次直接插入排序。
例子上面这个示意图正是希尔排序的实例，希尔排序通过每一小块的直接插入排序，并缩小增量，对更小的块进行直接插入排序，从而最后得到的必然是基本有序的序列，再进行一次直接插入排序，从而确定整个序列。
实现代码采用的是除2法123456789101112131415161718void ShellSort(List &L){ int i,j,temp; int d=L.size/2; while(d>0) { for(i=d;i<L.size;i++) { temp=L[i]; for(j=i-d;j>=0&&temp<L[j];j-=d) { L[j+d]=L[j]; ...
十大排序——选择排序
选择排序基本思想默然未排序区的首个元素为最小，然后与后面的最小元素交换，直至循环完成
实现代码12345678910111213141516void SelectSort(List &L){ int i,j; int minIndex=i; for(i=0;i<L.size-1;i++) //做第i趟排序,共n-1趟，因为第n趟只剩一个一定是最大的 { minIndex=i; for(j=i+1;j<L.size;j++) { if(L[minIndex]>L[j]) minIndex=j; } if(minIndex!=i) swap(L[minIndex],L[i]); }}
算法复杂度从i个记录中挑选最小记录需要比较i-1次。第i（i=0～n-2）趟从n-i记录中挑选最小记录需要比较n-i-1。对n个记录进行简单选择排序，所需进行的关键字的比较次数 总计为：移动记录的次数，正序为最小值 0，反序为最大值n-1 。 ...
十大排序——基数排序
基数排序基本思想基数排序分为两个步骤：分配（Distribute）和收集（Collect）分配是指分配一个存储链表的数组，第一个元素（链表）存储该位数上是0的元素，依次类推，共10个元素。收集是指将链表上的元素收集到原数组中。经过所有分配，最后收集到的一定是有序的。
例子这是对三位数的基数排序流程，要经过所有位的分配和收集。其最后收集到的数组是排序好的。
实现代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546int Getkey(int value,int k) //第k位的数{ int key; while(k>0) { key=value%10; value/=10; k--; } return key;}void Distribute(List &L,int k,list<int> *lists){ for(int i=0 ...
十大排序——快速排序
快速排序基本思想每趟使表的第1个元素放入适当位置（归位），并且左边的元素小于这个元素，右面的元素大于这个元素，我们称这个元素为pivot，将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为0或1（递归出口）。快速排序二叉递归树：正因为是将最左边的元素提取出来当pivot，所以左边都比它小，右边都比它大，继续划分也是如此，因此这个pivot在序列中的位置就已经决定好了，其他的序列继续如此划分，直至最后分到子表长度只有1或0。由于划分是按照整体有序的方式进行的，所以最后得到的序列必然是有序的。顺带一提，STL的sort的实现原理就是快速排序。因为相比冒泡等时间换空间的算法以及桶排序等空间换时间的算法来说，快排没有严重失衡，得到优化后更是如此，无愧于20世纪十大算法之一。
实现代码12345678910111213141516171819202122232425void QuickSort(List &L,int left,int right){ int l=left,r=right; //记录此时的左边界和右边边 int temp= ...
O(logn!)=O(nlogn)的证明
O(logn!)=O(nlogn)我们可以证明logn！小于nlogn而大于一个常数倍的nlogn(当n大于某一常数时）。下面给出推导过程：对于n>0，显然logn！<=nlogn是显然成立的接下来，证明logn！>=Cnlogn我们去掉前半部分，则可得:取最小项替代所有项，则：由于小于n/2logn，我们可以取其大于1/4logn:完整的步骤：所以O(lgn!)=O(nlogn)证毕
