INSERTION_SORT(A)forj=2tolength[A]dokey=A[j]i=j-1//将其与已经排好序的数组进行挨个比较whilei>0andA[i]>keydoA[i+1]=A[i]i=i-1A[i+1]=key原理
其实就是在每次进入一个元素key后，将其与已经排好序的序列进行比较，如果key值小于序列的第一个值（默认为从小到大排序），那么就表明该key应该置入这个序列当中，并且将比较过的元素自动向后移动，以腾出空间放置key。最后将key值置入空位中。
现实中就是在接牌时，插入和调整扑克牌顺序的问题了，算法复杂度为O(n^2)
分治法-分解-解决-合并
主要在于合并算法MERGE(A,p,q,r)伪代码如下：
MERGE(A,p,q,r)n1=q-p+1n2=r-qfori=1ton1doL[i]=A[p+i-1]forj=1ton2doR[j]=A[q+j]L[n1+1]=-ooR[n2+1]=-ooi=j=1fork=ptordoifL[i]<=R[j]thenA[k]=L[i]i=i+1elseA[k]=R[j]j=j+1原理
首先将输入数组分割，然后在对分割后的数组进行一一比较，如果L的元素小，就将其输出至目的数组A,如果R小，则输出R至A.
此时MERGE-SORT算法就清晰了，如果将一个数组通过递归不断将其分割，最终分割为每个数组只有一个元素，那么使用MERGE时，就能够将此二元素排序，然后对4元素排序，然后是8元素....伪代码如下:
MERGE-SORT(A,p,r)ifp 递归式T(n)=aT(n/b)+f(n),其中a>=1,b>1,f(n)是给定函数 仔细画出递归树 是求解递归式T(n)的食谱方法。主方法依赖于定理4.1主定理设a>=1和b>1为常数，设f(n)为一函数，T(n)由递归式 T(n)=aT(n/b)+f(n) 对非负整数定义，其中n/b指上顶或者下底，那么T(n)可能有如下的渐进界...主要是针对f(n),a,b等值。 概率分析，随机算法。使用概率分布预测输入值的分布，以此来帮助分析算法平均情况行为的。 I(A)=1，如果A发生的话；0，如果A不发生的话。 无法得到输入分布，考虑使用随机算法。随机排列数组许多随机算法通过排列给定的输入数组来使输入随机化。 在有限集合S上构造一个长度为k的串称为K串。直观上，为了在n元集上构造一个k串，有n种方法选择第一个元素，同样地，也有N种方法选择第二个元素，这样一次进行K次，从而K串的数目为nnn*...n=n^k.最形象的就是车牌号了。 有限集S的排列是S中所有元素的有序序列，且每个元素仅出现一次。一个N元集的集合有n!种排列，第一个元素有n种选择，第二个有n-1种选择，第三个有n-2种选择...集合S的k排列是S中k个元素的有序排列，且每个元素出现一次。因此N元集合的K排列数目是 n(n-1)(n-2)(n-3)(n-4)...(n-k+1)=n!/(n-k)! n元集的K组合就是S的k子集，n元集的k组合的数目可以用排列的数目来表示，对每个k组合，它的元素恰好有k!中排列，每个都是n元集的一个不同的k排列。因此，n元集的k组合数目是其k排列的数目除以k!。这个数量为 n!/(k!(n-k)!) 组合与排列的区别是，组合中k元祖是无序的，而排列是有序的，意味着组合的元祖对应着k！种不同的排列元祖。因此在计算时需要除去每个元祖的其他的有序排列。 下界 =n!/k!(n-k)!展开>=(n/k)^k 再利用斯特林近似式得上界 <=n^k/k!<=(en/k)^k 条件概率Pr{A|B}读作在事件B发生的条件下，事件A发生的概率 如果Pr{A交B}=Pr{A}Pr{B}，则称连个事件独立。 贝叶斯定理 Pr{A交B}=Pr{B}Pr{A|B}=Pr{A}Pr{B|A} 通过交换律，可得如下贝叶斯定理 Pr{A|B}=Pr{A}Pr{B|A}/Pr{B} 随机变量X的概率密度函数 f(x)=Pr{X=x} 随机变量的期望值 E[X]=∑xPr{X=x} 方差 Var[X]=E[(X-E[X]^2)]=E[X^2]-E^2[X] 几何分布假设进行一系列的伯努利实验，每次实验成功的概率是P，失败的概率是q=1-p,在取得一次成功前要进行多少次实验？因为在取得一次成功前有k-1次失败，从而有 Pr{X=k}=q^(k-1)p 期望1/p 二项分布因为有(nk)种方法从n次实验中选取k次成功的试验，且每次发生的概率是p^k*q^(n-k)