Java与算法（一）
一冒泡排序
冒泡排序法的原理是，每次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。
例如对4362715这7个数字进行从小到大的排序，从最左侧开始，首先比较4和3
例如对4362715这7个数字进行从小到大的排序，从最左侧开始，首先比较4和3
因为是从小到大排序，4和3的顺序显然是错误的，交换他们，得到
接下来比较4和6
顺序是正确的，不需要任何操作。接下来进行下一步，比较6和2
6显然应该排在2的后面，怎么办？交换它们，得到
经过前面几步，已经可以总结出规律，那么接下来要做的比较依次是：
7>1?得到3426175
7>5?得到
到此，7的右边已经没有数可以比较，第一轮排队结束。经过这一轮，已经成功的把最大的数，即7放在了最后。但是前面6个数的顺序还是不对，但是按照上面的思路很容易想到，对前面6个数再来一遍，即可把6放到倒数第二的位置。然后再对前面5个数重复逐个比较的步骤。。。
7个数字需要进行7-1=6次排队，每完成一轮排队，下一轮排队需要比较的数字个数减1，来看代码
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicclassBubbleSort{
publicvoidsort(int...numbers){
//n个数执行n-1轮
//每一轮后完成一个数字归位,下一轮要比较的数字个数减1(所以内层循环是j
intn=numbers.length-1;
intt;
for(inti=0;i
for(intj=0;j
if(numbers[j]>numbers[j+1]){
t=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=t;
}
}
}
}
}
测试
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicstaticvoidmain(String[]args){
int[]numbers=newint[]{4,3,6,2,7,1,5};
System.out.print("before:");
for(inti=0;i
System.out.print(numbers[i]+"");
}
System.out.println();
newBubbleSort().sort(numbers);
System.out.print("after:");
for(inti=0;i
System.out.print(numbers[i]+"");
}
System.out.println();
}
输出
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
before:4362715
after:1234567
冒泡排序的核心是两层嵌套的循环，时间复杂度是O(N^2)，即对N个数排序，需要近似执行N的平方次。因为效率较低，实际开发中基本不会使用，但是因为简单易懂通常做为学习算法的入门案例。
如果用上面的代码对1234567做从小到大排列，会发现虽然数字已经排列好，但是程序还是要忠实的执行完全部两层循环。对这种情况，我们可以引入一个变量来记录一次内层循环中交换数字的个数，如果交换个数为0，则提前终止循环，在某些情况下可以提高效率。
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicvoidbetterSort(booleandescend,int...numbers){
System.out.print("before:");
for(inti=0;i
System.out.print(numbers[i]+"");
}
System.out.println();
//n个数执行n-1轮
//每一轮后完成一个数字归位,下一轮要比较的数字个数减1(所以内层循环是j
intn=numbers.length-1;
intt;
intflag=0;
for(inti=0;i
for(intj=0;j
if(descend){//从大到小
if(numbers[j]
t=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=t;
flag=1;
}
}else{
if(numbers[j]>numbers[j+1]){
t=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=t;
flag=1;
}
}
}
if(flag==0){
break;
}else{
flag=0;
}
}
System.out.print("after:");
for(inti=0;i
System.out.print(numbers[i]+"");
}
System.out.println();
}
增加一个变量需要额外占用内存空间，因此，这个方法是以空间换时间。
二快速排序
选定最左侧数字4为基准数，首先从右开始向左找小于4的数，找到第一个数1后停止。然后从左开始向右找到第一个大于4的数，即6。
交换这两个数的位置，得到
继续寻找，仍然从右边开始，从上一步找到1的位置向左寻找小于4的数，找到2停止。然后从左边找到6的位置向右找大于4的数。右移一格后，和右侧来的“探路者”相遇了，这意味着这一轮排序结束。
最后把结束位置的数和基准数交换
观察完成后的数列，可以看到以基准数4为分界线，左边的数全都比4小，右边的数全都比4大。接下来分别对左边的231和右边的765重复上面的排序步骤。
231
以2为基准数->213->123
765
以7为基准数->567
我们例子中的数字较少，如果数列足够长，对第一次排序后得到的子数列排序，将再得到两个子数列，然后再一分为二、二分为四。。。直到以基准数拆分后两边都只剩下一个数字。首先来看递归形式的实现代码
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicclassQuickSort{
publicvoidsort(intleft,intright,int...numbers){
if(left>=right){
return;
}
inttemp=numbers[left];
intt=0;
inti=left;
intj=right;
while(i!=j){
//先从右往左找
while(numbers[j]>=temp&&i
j--;
//再从左往右找
while(numbers[i]<=temp&&i
i++;
//交换两个数在数组中的位置
if(i
t=numbers[i];
numbers[i]=numbers[j];
numbers[j]=t;
}
}
//将基准数归位
numbers[left]=numbers[i];
numbers[i]=temp;
sort(left,i-1,numbers);
sort(i+1,right,numbers);
}
}
测试代码
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicstaticvoidmain(String[]args){
int[]numbers=newint[]{4,3,6,2,7,1,5};
newQuickSort().sort(0,numbers.length-1,numbers);
System.out.print("after:");
for(inti=0;i
System.out.print(numbers[i]+"");
}
System.out.println();
}
输出
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
after:1234567
另一种实现方式是使用栈代替递归
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicvoidsortWithoutRecursion(intleft,intright,int...numbers){
LinkedListstack=newLinkedList<>();
intindex;
stack.push(left);
stack.push(right);
while(!stack.isEmpty()){
right=stack.pop();
left=stack.pop();
index=partition(left,right,numbers);
if(left
stack.push(left);
stack.push(index-1);
}
if(right>index+1){
stack.push(index+1);
stack.push(right);
}
}
}
publicintpartition(intleft,intright,int...numbers){
inttemp=numbers[left];
while(left
while(numbers[right]>=temp&&left
right--;
numbers[left]=numbers[right];
while(numbers[left]<=temp&&left
left++;
numbers[right]=numbers[left];
}
numbers[left]=temp;
returnleft;
}
三斐波那契数列
首先手工计算来总结规律，如下表
注意总数这一列
1+1=2
1+2=3
2+3=5
3+5=8
5+8=13
可以得出规律，第n个斐波那契数=第n-1个斐波那契数+第n-2个斐波那契数
为了计算n，必须计算n-1和n-2；为了计算n-1，必须计算n-2和n-3；直到n-x的值为1为止，这显示是递归大显身手的地方。来看代码
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicclassFibonacci{
publicstaticlongcalc(longn){
if(n<0){
return0;
}
if(n==0||n==1){
returnn;
}else{
returncalc(n-1)+calc(n-2);
}
}
}
这真是极短的，测试代码
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicstaticvoidmain(String[]args){
longn=50;
longbegin=System.nanoTime();
longf=Fibonacci.calc(n);
longend=System.nanoTime();
System.out.println("第"+n+"个斐波那契数是"+f+",耗时"+TimeUnit.NANOSECONDS.toMillis(end-begin)+"毫秒");
}
运行输出
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
第50个斐波那契数是12586269025,耗时66024毫秒
注意看消耗的时间，在我的电脑上耗时66秒，真是个相当耗时的操作。既然整个过程都是在不断重复相同的计算规则，那我们可以采用分而治之的思想来优化代码。
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
importjava.util.concurrent.ForkJoinPool;
importjava.util.concurrent.RecursiveTask;
importjava.util.concurrent.TimeUnit;
publicclassFibonacciextendsRecursiveTask{
longn;
publicFibonacci(longn){
this.n=n;
}
publicLongcompute(){
if(n<=10){//小于10不再分解
returnFibonacci.calc(n);
}
Fibonaccif1=newFibonacci(n-1);//分解出计算n-1斐波那契数的子任务
f1.fork();//由ForkJoinPool分配线程执行子任务
Fibonaccif2=newFibonacci(n-2);//分解出计算n-2斐波那契数的子任务
returnf2.compute()+f1.join();
}
publicstaticlongcalc(longn){
if(n<0){
return0;
}
if(n==0||n==1){
returnn;
}else{
returncalc(n-1)+calc(n-2);
}
}
publicstaticvoidmain(String[]args){
longn=50;
longbegin=System.nanoTime();
Fibonaccifibonacci=newFibonacci(n);
ForkJoinPoolpool=newForkJoinPool();
longf=pool.invoke(fibonacci);
longend=System.nanoTime();
System.out.prinwww.shanxiwang.nettln("第"+n+"个斐波那契数是"+f+",耗时"+TimeUnit.NANOSECONDS.toMillis(end-begin)+"毫秒");
}
}
运行输出
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
第50个斐波那契数是12586269025,耗时20461毫秒
虽然时间缩短了2/3，但是仍然不理想。回头重新看计算方法，用递归方式虽然代码简短，但是存在很严重的重复计算，下面用非递归的方式改写，过程中每个数只计算一次。
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicstaticlongcalcWithoutRecursion(longn){
if(n<0)
return0;
if(n==0||n==1){
returnn;
}
longfib=0;
longfibOne=1;
longfibTwo=1;
for(longi=2;i
fib=fibOne+fibTwo;
fibTwo=fibOne;
fibOne=fib;
}
returnfib;
}
测试
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
第50个斐波那契数是12586269025,耗时0毫秒
斐波那契数的另一个经典题目是青蛙跳台阶问题：
一只青蛙一次可以条一级或两级台阶，求该青蛙跳上n级的台阶共有多少种跳法。
假设计算第n级台阶跳法的函数是f(n)，当n>2时，第一步选择跳一级有X种跳法，第一步选择跳两级有Y种跳法，f(n)=X+Y。如何计算X呢，站在青蛙的位置考虑，面对的是一个全新的n-1级台阶，有f(n-1)种跳法，那么Y就是n-2级台阶的跳法，那么f(n)=f(n-1)+f(n-2)，即斐波那契数列公式。
四数字全排列
全排列是指n个数(或其他字符)所有可能的排列顺序，例如123三个数字的全排列是
123
132
213
231
312
321
那么问题来了，任意输入一个大于1的数字n，列出1-n这n个数字的全排列。
如果尝试手动列举一下123的全排列，会发现通常我们会在头脑中制定好规则，并按照既定规则进行枚举，从而得到所有排列。
在这里我们制定的规则是：
（想象我们手里拿了3个数字，地上有A、B、C三个空位）
1)在每一个空位前，都按照1->2->3的顺序尝试放下一个数字，如果该数字已经放下则尝试下一个
2)每放下一个数字后向后移动一格，然后重复1->2->3的尝试
3)如果当前位置没有新的可能性，取回当前位置的数字并左移一格从新尝试
按上面规则很容易推算出第一种排列是123
取回3，返回B位置，取回2，然后按1->2->3尝试，发现可以放下3，右移到C，尝试后放下2，得到132
接下来必须返回到A的位置才有新的可能性，此时已经取回所有数字，按规则放下2，移到B，放下1，移到C，放下3，得到213
。。。
下面来看实现的代码：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicclassPermutation{
privateintmax;
privateint[]array;
privateint[]hold;
publicPermutation(intmax){
this.max=max;
array=newint[max+1];
hold=newint[max+1];
}
publicvoidpermute(intstep){
if(step==max+1){
for(inti=1;i<=max;i++){
System.out.print(array[i]+"");
}
System.out.println();
return;//返回上一步,即最近一次调用permute方法的后一行
}
//按照1->2->3->...->n的顺序尝试
for(intnum=1;num<=max;num++){
//判断是否还持有该数字
if(hold[num]==0){
array[step]=num;
hold[num]=1;
//递归:右移一格重复遍历数字的尝试
permute(step+1);
//回到当前位置时取回当前位置数字
hold[num]=0;
}
}
}
publicstaticvoidmain(String[]args){
Permutationfa=newPermutation(3);
fa.permute(1);
}
}
运行输出
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
123
132
213
231
312
321
我们用一个伪时序图来帮助理解递归调用的执行过程
顺便说一句，全排列问题还有多种算法，本文中使用的是深度优先算法的模型。
五老鼠走迷宫(深度优先算法)
小老鼠走进了格子迷宫，如何能绕过猫并以最短的路线吃到奶酪呢？
注意只能上下左右移动，不能斜着移动。
在解决迷宫问题上，深度优先算法的思路是沿着一条路一直走，遇到障碍或走出边界再返回尝试别的路径。
首先用一个二维数组来把迷宫“数字化”。
迷宫中每个格子的横纵坐标对应数组的一维和二维索引，例如最左上角的格子是maze[0][0]，数组的值表示该格子是否可以通过，0表示可以通过，1表示该格子有猫。
初始化迷宫，标记猫的位置：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
this.maze[2][0]=1;
this.maze[1][2]=1;
this.maze[2][2]=1;
this.maze[3][2]=1;
起点位置坐标是x=0，y=0，如果向右移动就是x=x+1,y=y，向下移动是x=x,y=y+1。我们预先规定每到一个格子都按照右、下、左、上的顺序尝试下一个格子是否能走，如果右边的格子没有猫且未出边界，就移动到下一个格子，继续按照右、下、左、上的顺序尝试；如果右边的格子不能走则尝试下面的格子。
下面这个二维数组用来遍历尝试四个方向的格子：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
int[][]next=newint[][]{
{1,0},
{0,1},
{-1,0},
{0,-1}
};
为了不走回头路，我们还需要另外一个二维数组标记哪些格子是已走过的，如果已走过则不能回头。
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
int[][]mark=newint[5][4];
用一个栈记录路径
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
LinkedListmap=newLinkedList<>();
走格子的思路是：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
for(遍历四个方向的格子){
if(格子超出边界或格子有猫或格子已经走过){
continue;
}else{
移动到格子
记录当前格子已走过
记录当前路径
for(以新格子为中心遍历四个方向的格子){
......
}
}
}
但是我们并不知道要走多少步才能到达目标，也就不知道循环要嵌套多少层，但是可以看出每次新的遍历循环开启后，执行的代码和上一层循环是一样的，所以这里用递归解决。来看完整的代码：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
importjava.util.LinkedList;
publicclassDfsRatMaze{
intmin=Integer.MAX_VALUE;
intendX=3;//目标点横坐标
intendY=3;//目标点纵坐标
intwidth=5;//迷宫宽度
intheight=4;//迷宫高度
int[][]maze=newint[5][4];
int[][]mark=newint[5][4];
LinkedListmap=newLinkedList<>();
publicvoiddfs(intstartX,intstartY,intstep){
int[][]next=newint[][]{//按右->下->左->上的顺序尝试
{1,0},
{0,1},
{-1,0},
{0,-1}
};
intnextX,nextY;
intposible;
if(startX==endX&&startY==endY){
if(step
min=step;
for(inti=map.size()-1;i>=0;i-=2){
nextX=map.get(i);
nextY=map.get(i-1);
System.out.print("["+nextX+","+nextY+"]");
if(i!=1)
System.out.print("->");
}
System.out.println();
return;
}
for(posible=0;posible下->左->上的顺序尝试
nextX=startX+next[posible][0];
nextY=startY+next[posible][1];
if(nextX<0||nextX>=width||nextY<0||nextY>=height){//超出边界
continue;
}
if(maze[nextX][nextY]==0&&mark[nextX][nextY]==0){//非障碍且未标记走过
map.push(nextX);
map.push(nextY);
mark[nextX][nextY]=1;
dfs(nextX,nextY,step+1);//递归调用,移动到下一格
mark[nextX][nextY]=0;
map.pop();
map.pop();
}
}
}
/
初始化迷宫
/
publicvoidinitMaze(){
this.maze=newint[width][height];
this.mark=newint[width][height];
this.maze[2][0]=1;
this.maze[1][2]=1;
this.maze[2][2]=1;
this.maze[3][2]=1;
this.mark[0][0]=1;
//打印迷宫_表示可通行表示障碍!表示目标
for(inty=0;y
for(intx=0;x
if(x==endX&&y==endY){
System.out.print("!");
}elseif(this.maze[x][y]==1){
System.out.print("");
}else{
System.out.print("_");
}
}
System.out.println();
}
System.out.println();
}
publicstaticvoidmain(String[]args){
intstartX=0;
intstartY=0;
DfsRatMazed=newDfsRatMaze();
d.initMaze();
d.dfs(startX,startY,0);
if(d.min
System.out.println("最少需要"+d.min+"步");
else
System.out.println("目标地点无法到达");
}
}
运行后输出：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
[1,0]->[1,1]->[2,1]->[3,1]->[4,1]->[4,2]->[4,3]->[3,3]
[1,0]->[1,1]->[2,1]->[3,1]->[3,0]->[4,0]->[4,1]->[4,2]->[4,3]->[3,3]
[1,0]->[1,1]->[0,1]->[0,2]->[0,3]->[1,3]->[2,3]->[3,3]
[0,1]->[1,1]->[2,1]->[3,1]->[4,1]->[4,2]->[4,3]->[3,3]
[0,1]->[1,1]->[2,1]->[3,1]->[3,0]->[4,0]->[4,1]->[4,2]->[4,3]->[3,3]
[0,1]->[0,2]->[0,3]->[1,3]->[2,3]->[3,3]
最少需要6步
可以看到，程序计算出了所有路线，并找到了最短的路线。而整个代码还不到100行，真是神奇的算法。
|
|
