江苏龙网

  1. 主页 > 生活百科 > >

java五大常用算法，早看早知道( 二 )

算法


--right;
}
swap(array,left,right);
}
swap(array,right,count);
return right;
}
/**
*分治思想 ， 递归调用
*/
static void QuickSort(int array[],int left,int right)
{
if(left >= right)//表示已经完成一个组
{
return;
}
int index = PartSort(array,left,right);//枢轴的位置
QuickSort(array,left,index - 1);
QuickSort(array,index + 1,right);
}
public static void main(String[] args) {
int a[]= {1,5,-5,54,15,67,16,23};
QuickSort(a,0,7);
for(int i=0;i<a.length;i++) {
System.out.print(" "+a[i]);
}
System.out.print("n");
}
}
算法心得
作为分治法里很典型的一种算法 ， 合并排序和快速排序充分展现了分治法的思想 ， 分而治之 ， 在此次编程使用此方法中 ， 给我的体会是程序简单分为两部分 ， 第一部分 ， 不断“拆” ， 缩小子问题规模 ， 达到最优子结构 。然后合并 ， 在合并过程中 ， 应为子问题足够小 ， 容易计算 ， 再者不断合并子问题答案 ， 最终求出问题解 。

java五大常用算法，早看早知道

文章插图
 
算法二：贪心算法
一、基本概念：
所谓贪心算法是指 ， 在对问题求解时 ， 总是做出在当前看来是最好的选择 。也就是说 ， 不从整体最优上加以考虑 ， 他所做出的仅是在某种意义上的局部最优解 。
贪心算法没有固定的算法框架 ， 算法设计的关键是贪心策略的选择 。必须注意的是 ， 贪心算法不是对所有问题都能得到整体最优解 ， 选择的贪心策略必须具备无后效性 ， 即某个状态以后的过程不会影响以前的状态 ， 只与当前状态有关 。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性 。
二、贪心算法的基本思路：
1.建立数学模型来描述问题 。
2.把求解的问题分成若干个子问题 。
3.对每一子问题求解 ， 得到子问题的局部最优解 。
4.把子问题的解局部最优解合成原来解问题的一个解 。
三、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解 。
实际上 ， 贪心算法适用的情况很少 。一般 ， 对一个问题分析是否适用于贪心算法 ， 可以先选择该问题下的几个实际数据进行分析 ， 就可做出判断 。
四、贪心算法的实现框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策 ， 求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
五、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解 ， 因此 ， 一定要注意判断问题是否适合采用贪心算法策略 ， 找到的解是否一定是问题的最优解 。
贪心策略例题：prim算法
import JAVA.util.*;
public class 贪心算法_prim算法 {
static int MAX = Integer.MAX_VALUE;
public static void main(String[] args) {
//定义无向图矩阵
int[][] map = new int[][] {
{ 0, 1, 6, 2},
{ 1, 0, 3, 2},
{ 6, 3, 0, 1},
{ 2, 2, 1, 0}
};
prim(map, map.length);
}
public static void prim(int[][] graph, int n){
//定义节点名字
char[] c = new char[]{'A','B','C','D'};
int[] lowcost = new int[n]; //到新集合的最小权
int[] mid= new int[n];//存取前驱结点
List<Character> list=new ArrayList<Character>();//用来存储加入结点的顺序
int i, j, min, minid , sum = 0;
//初始化辅助数组
for(i=1;i<n;i++)
{
lowcost[i]=graph[0][i];
mid[i]=0;
}
【java五大常用算法，早看早知道】list.add(c[0]);
//一共需要加入n-1个点
for(i=1;i<n;i++)
{
min=MAX;
minid=0;
//每次找到距离集合最近的点
for(j=1;j<n;j++)
{
if(lowcost[j]!=0&&lowcost[j]<min)
{
min=lowcost[j];
minid=j;
}
}
if(minid==0) return;
list.add(c[minid]);
lowcost[minid]=0;
sum+=min;
System.out.println(c[mid[minid]] + "到" + c[minid] + " 权值：" + min);


推荐阅读


上一篇：中国茶企核心竞争力缺失缘由何在

下一篇：茶经立顿并用 整合资源做强中国茶