O：O(g(n))表示，当n足够大，0≤f(n)≤g(n)，也就是上界
Ω：相对于O，Ω表示下界
Θ：相当于O和Ω，Θ表示刚好相等
宏：f(n)=n³+O(n²)表示存在一个确切的f(n)
稳定性：保证相等的元素顺序。
找到数组中(序号从小到大)第一个无序的元素，与前面的元素大小作比较，找到使得他们有序的位置，把这个元素提到前面即可。如果没有找到这个位置，说明不用改变位置。找完这一流程后去找下一元素的排序，直到找完整个数组。
时间复杂度:O(n²)
1.如果数组长度为1，直接结束。
2.递归地对当前数组(数组的一部分)的0~(n/2)+1的这一部分和(n/2)+1~n排序。
3.合并两个数组，使得他们有序。
时间复杂度(n>1)：O(nlogn)(T(n)=2T(n/2)+O(n))
quicksort(Array[] A,int p,int q)
1.分治算法
2.就在原来的数组里进行重排
选取一个关键数据，以这个数为基准，把数组分为两个区域，一个区域里的数都大于这个基准，而另一个区域的数都小于这个基准。之后对每个区域进行递归，继续选取基准。直到数据有序。
对于一个数组，选取一个==主元==(通常是第一个元素)。同时初始化时有两个指针，i=0，j=i+1。j开始逐个向右扫描，直到找到第一个小于主元的数，把它和i+1互换，i和j再加一(此使j一般不等于i+1，主元也会变成那个小于原来主元的数)。继续循环，循环结束后还需要把当前的主元与最开始定义的主元互换，这样主元左边的都小于主元，而右边的都大于主元了。然后再继续对主元两边的子数组进行递归。
| 6(i) | 10(j) | 13 | ==5== | 8 | 3 | 2 | 11 |
|---|
| 6(i) | 5 | 13 | 10 | 8(j) | ==3== | 2 | 11 |
|---|
| 6(i) | 5 | 3 | 10 | 8 | 13 | ==2==(j) | 11 |
|---|
| 6(i) | 5 | 3 | 2 | 8 | 13 | 10 | 11(j) |
|---|
| 2 | 5 | 3 | 6* | 8 | 13 | 10 | 11 |
|---|
时间复杂度
最坏情况：每一次分化正好在边界上，要对n-1长度的数组进行递归。T(n) = O(n²)
最好情况：每一次分化在最中间大小的数，仅仅对n/2长度的数组进行递归。T(n) = 2T(n/2) + Θ(n) = Θ(nlogn)
平均情况lucky：除开最坏情况和最好情况其他划分情况时间复杂度计算均为O(nlogn)
public void quicksort(int[] array,int p,int q){
if(p>=q) return;
int i = p;
int j = p+1;
int basej = j;
while(j<=q){
if(array[i]>=array[j]){
int temp = array[j];
array[j] = array[basej];
array[basej] = temp;
basej++;
}
j++;
}
int temp = array[i];
array[i] = array[basej-1];
array[basej-1] = temp;
quicksort(array,0,basej-2);
quicksort(array,basej,q);
}如果随机的选取主元或是随机排列序列元素。那么该算法的效率依然不会改变。
即最差的情况不会由输入导致，而是机器产生的随机数决定。
在随机的情况下，该算法的平均时间复杂度为O(nlogn)，一般比归并排序的速率快3倍以上，但不能像归并一样保证O(nlogn)的最坏情况。
快速选择：在快速排序的基础上，它只需要递归处理处理一边的情况。一般用于找第i个最大值或最小值。每次选取主元并分区后判断主元的位置是否为i，是就直接返回。不是则递归一边，直到找到为止。
局限性：不能进行整数相乘或者是其他奇怪的操作。
使用决策树对选择排序进行分析。对于长为n的所有输入(排序n个元素)，决策树的深度最小为nlogn。
两种比nlogn快的算法
1.计数排序(适用于元素范围较小)
通常输入是一个数列，但会设定这些元素的范围1~k。实际上的运行时间也会与k有关。因此，这个k越小越好。
需要一些==辅助存储序列==(出现频率等)。
//算法过程
/*
1.使用c[i]来记录某些数值出现的频率。
2.对数组A中每个值A[j]，递增代表A[j]的计数器的值。
3.c[i]会给出数组中等于数值i的元素的数量。
4.借助c计算小于等于i的元素的数量，用一个c'数组保存。
5.分配。在原数组中从后往前遍历。通过c'可以计算出最后一个数i当前所在的位置为c'[i]，把它分配到新数组c'[i]的位置，同时让c'[i]减去1。在最终完成遍历，新数组即为排好序的数组
*/
//时间复杂度：O(k+n)，如果k越小，那么这个算法越快。2.基数排序
以斐波那契数列为例，时间复杂度=(1、1，1、0)^n.
解决递归的方法：
1.代换法
根据递归式猜测当前的复杂度，然后用数学归纳法证明
1.主方法(限制较多，只能用到特定的递归式上)
适用于T(n) = aT(n/b) + f(n) ，即每个子问题的规模都相等的递归式且b>1.
思路：比较f(n)和n^logba
- 如果f(n)比较小，T(n) = Θ(n^logba)
- 如果差不多相等，T(n) = Θ(n^logba * logn^(k+1))【f(n)中包含logn的k次方】
- 如果f(n)比较大，T(n) = Θ(f(n))
==2.构造递归树==
例如T(n)=2T(n/2)+cn，则递归树可构造成
cn
/ \
T(n/2) T(n/2)
每个T(n/2)又可以继续向下==递归构造==，一直到叶节点。这颗递归树的高度是==logn==，它的叶节点有==n==个，每一个均为O(1)。
递归树的每一行都有着某种规律，因此把他们全部加起来一般情况是一个级数。
时间复杂度：递归树的每一个结点相加。
=cn*(logn)+Θ(1)=Θ(nlogn)
1.把一个大问题分解成很多个子问题
2.解决这些子问题
3.合并这些子问题，从而解决大问题
ex：归并排序、二分查找、斐波那契数列
ex2：计算x的n次方，把他分解成两个X的n/2次访相乘。
ex3：矩阵的乘积。如果一层一层遍历的话时间复杂度为O(n³)，采用分治法做出改进。
改进1：分块矩阵。思想与分治法契合，T(n) = 8T(n/2)+Θ(n²)=O(n³)，时间上并没有改进。
分治时间复杂度为O(n)的情况：H布局
中间是根节点，四个角落分别有n/4个叶节点。两边的L(n)=2L(n/4)+Θ(1)，使用主方法计算得到O(n^1/2).
决策树是一种规定了能够进行哪些操作的模型。决策树把算法中所有可能比较的结果都列了出来。或是说，指出了所有的路线。
决策树上的每一个结点表示一次操作，根据操作的结果，来选择要走哪一条路径。走到决策树的叶子结点时，就表示找到了一种完整的方法。
例如：对三个元素进行排序，先比较a1和a2的大小，根据大小再一次比较较大者或较小者与a3的大小，最后得到排序的顺序。
~~记录一个算法的时候并不是一个很方便的表达。~~决策树有时会呈指数级增长。
xxx哈希表示的是哈希算法，及通过这种算法来计算出元素的哈希码，根据哈希码插入到哈希表中指定的位置。
每个k-v都有==相同的概率==被哈希映射到哈希表中的任何一个槽。