概述
什么是算法：
任何定义明确的计算步骤都可称为算法，接受一个或一组值为输入，输出一个或一组值。(来源：homas H. Cormen, Chales E. Leiserson 《算法导论第3版》)
算法3特征：
[1] 有穷性。执行有限步骤后，算法必须中止。
[2] 确切性。算法的每个步骤都必须确切定义。
[3] 可行性。特定算法须可以在特定的时间内解决特定问题。
十大算法
归并排序(MERGE SORT)，快速排序(QUICK SORT)和堆积排序(HEAP SORT)
傅立叶变换和快速傅立叶变换
代克思托演算法 (Dijkstra’s algorithm)
RSA非对称加密算法
哈希安全算法(Secure Hash Algorithm)
整数质因子分解算法(Integer factorization)
链接分析算法(Link Analysis)
比例微积分算法(Proportional Integral Derivative Algorithm)
数据压缩算法
随机数生成算法
java面试算法
排序和查找算法
排序：将一组杂乱无章的数据按一定的规律顺次排列起来。
数据表( data list): 它是待排序数据对象的有限集合。
排序码(key):通常数据对象有多个属性域，即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。
分类
内排序：指在排序期间数据对象全部存放在内存的排序；
外排序：指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
排序算法的稳定性
如果在对象序列中有两个对象r[i]和r[j] ,它们的排序码k[i]==k[j] 。如果排序前后,对象r[i]和r[j] 的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。
时间开销
排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。
算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算
空间开销
算法执行时所需的附加存储。
直接插入排序
基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
伪代码：
for i = 1, n
j = i//待排序的记录
while(E[j] < E[j-1])
swap(E[j], E[j-1])
j--
public static void insertSort(int arr[]) {
int temp = 0;
for (int i = 1; i < arr.length - 1; i++) {
int j = i;
while (arr[j] < arr[j - 1]) {
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
j--;
}
}
快速排序
http://developer.51cto.com/art/201403/430986.htm(推荐)
https://www.cnblogs.com/MOBIN/p/4681369.html
public static void quickSort(int arr[], int low, int high) {
if (arr == null) {
return;
}
// 如果左边大于右边，则return，这里是递归的终点，需要写在前面。
if (low >= high) {
return;
}
int i = low;
int j = high;
int key = arr[low];
if (low < high) {
while (i < j) { // 此处的while循环结束，则完成了元素key的位置调整
while (i < j && key <= arr[j]) {
j--;
}
arr[i] = arr[j];
while (i < j && key >= arr[i]) {
i++;
}
arr[j] = arr[i];
arr[i] = key; // 此处不可遗漏 将基准值插入到指定位置
}
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}
}
单链表
二叉树
队列和栈
字符串
数组
其它算法
参考
https://blog.csdn.net/lg1259156776/article/details/48665337
http://gitbook.cn/books/59f6a752d97c2122653a169e/index.html
http://blog.51cto.com/ahalei
