复制算法

为了解决标记清除算法内存碎片化严重的缺陷，提出了复制算法。复制算法主要思想是，按内存容量将内存划分为大小相等的两块区域。每次只使用其中一块，当这一块内存满后将其中存活的对象复制到另一块上去，然后把该内存中的垃圾对象清理掉，其实现过程如图：

复制算法虽然实现简单，内存效率高，不易产生碎片，但是最大的问题是可用内存被压缩到了原本的一半。且存活对象增多的话，Copying 算法的效率会大大降低。

复制算法

复制算法是将内存划分为两个区间，在任意时间点，所有动态分配的对象都只能分配在其中的一个区间（称为活动区间），而另外一个区间（空闲区间）是空闲的。

当有效内存空间耗尽时，JVM将暂停程序运行，开启复制GC线程。接下来GC线程会将活动区的存活对象，全部复制到空闲区间，且严格按照内存地址依次排列，与此同时，GC线程将更新存活对象的内存引用地址指向新的内存地址。

此时，空闲区间已经与活动区间交换，而垃圾对象现在已经全部留在了原来的活动区间，也就是现在的空闲区间。事实上，在活动区间转换为空闲区间的同时，垃圾对象已经被一次性全部回收了。

开始时：

在被GC线程处理后：

可以看到，1和4号对象被清楚了，而2，3，5，6号对象则是规则的排列在刚才的空闲区间，也就是现在的活动区间之间，此时左半部分已经变成空闲区间，然而，在下一次GC之后，左半部分再次变成活动区间。

显然：

复制算法缺点时非常明显的：

1.直接浪费了一般的内存。

2.再就是加入对象存活率非常高，达到了极端的100%，那么我们需要将所有的对象都复制一遍，并将所有引用地址重置一遍。复制这一工作所花费的时间，在对象存活率达到一定的程度时，将会变得不可忽视。

由此可见，复制算法要想使用，最起码对象的存活率要非常低才行，而且最重要的是，我们必须要克服50%内存浪费。

标记整理算法

分为两个阶段：

1.标记：遍历GC roots,然后将存活的对象标记。

2.整理：移动所有存活的对象，且按照内存地址次序依次排列，然后将末端内存地址以后的内存全部回收，这个阶段才为整理阶段。

它与GC 前后与复制算法类似，只不过没有了活动区间和空闲区间

倘若此时GC线程开始工作，那么紧接着开始的就是标记阶段了。此阶段与标记/清除算法的标记阶段是一样一样的，我们看标记阶段过后对象的状态，如下图。

接下来，便应该是整理阶段了。我们来看当整理阶段处理完以后，内存的布局是如何的，如下图。

%floyd.m

function [D,R]= floydwarshall(A)

% %采用floyd算法计算图中任意两点之间最短路程，可以有负权。

%参数D为连通图的权矩阵

%R是路由矩阵

D=An=length(D) %赋初值

for(i=1:n)for(j=1:n)R(i,j)=jendend %赋路径初值

for(k=1:n)

for(i=1:n)

for(j=1:n)

if(D(i,k)+D(k,j)<D(i,j))D(i,j)=D(i,k)+D(k,j) %更新dij，说明通过k的路程更短

R(i,j)=kendendend %更新rij，需要通过k

k %显示迭代步数

D %显示每步迭代后的路长

R %显示每步迭代后的路径

pd=0for i=1:n %含有负权时

if(D(i,i)<0)pd=1breakendend %跳出内层的for循环 存在一条含有顶点vi的负回路

if(pd==1) fprintf('有负回路')breakend %存在一条负回路, 跳出最外层循环 终止程序

end %程序结束

dij matlab算法

function [d,path]=dijkstra(W,s,t)

[n,m]=size(W)ix=(W==0)W(ix)=inf

if(n~=m),error('Square W requred')end

visited(1:n)=0dist(1:n)=infparent(1:n)=0dist(s)=0d=inf

for i=1:(n-1),

ix=(visited==0)vec(1:n)=infvec(ix)=dist(ix)

[a,u]=min(vec)visited(u)=1

for v=1:n,if(W(u,v)+dist(u)<dist(v)),

dist(v)=dist(u)+W(u,v)parent(v)=u

endendend

if(parent(t)~=0),path=td=dist(t)

while(t~=s),p=parent(t)path=[p path]t=pend

end

---