用java冒泡排序和递归算法

用java冒泡排序和递归算法

冒泡排序：
public class Test
{
public static void main(String[] args)
{

int[] array={1,2,6,8,9,3,4};
int temp=0;
for(int i=0;i<array.length;i++)
{
for(int j=i+1;j<array.length;j++)
{
if(array[i]>array[j])
{
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
System.out.println(array[i]+" ");
}

}
}
递归的用法：
public class Test {
char array_char[];
List lists=new ArrayList();
public int getInstances(String all, String choice) {
int total=0;
array_char=all.toCharArray();
for(int i=0;i<array_char.length;i++){
if (array_char[i]==(choice.charAt(0))){
total++;
}
}
return total;
} public static void main(String[] args) {
Test test=new Test();
String str="144745741258444174584";
List array=test.result(str);
for(int i=0;i<array.size();i++)
{
System.out.println(array.get(i)+" 出现的次数："+test.getInstances(str, array.get(i).toString()));
}
}
public List result(String str)
{
String st="";
if(str.length()>0)
{
lists.add(str.substring(0,1));
st=str.replaceAll(str.substring(0,1),"");
result(st);
}
return lists;
}
}2012-12-26

　　冒泡排序
　　（1）基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
　　（2）用java实现
ubli cclass bubbleSort { public bubbleSort(){ int a[]={1,54,6,3,78,34,12,45}; int temp=0; for(int i=0;i<a.length;i++){ for(int j=i+1;j<a.length;j++){ if(a[i]>a[j]){ temp=a[i]; a[i]=a[j]; a[j]=temp; } } } for(int i=0;i<a.length;i++) System.out.println(a[i]); } }　　递归
　　递归算法，就是程序的自身调用。表现在一段程序中往往会遇到调用自身的那样一种coding策略，可以利用大道至简的思想，把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。能看到我们会用很少的语句解决了非常大的问题，所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。
　　java代码：
package com.cjq.filedown; public classFab { public static void main(String args[]){ System.out.println(fab(5)); } private static int fab(int index){ if(index==1 || index==2){ return 1; }else{ return fab(index-1)+fab(index-2); } } }2015-11-03

冒泡排序算法的运作如下：（从后往前）
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元3. 素应该会是最大的数。
4. 针对所有的元素重复以上的步骤，除了最后一个。
5. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
递归算法
递归算法流程
递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数

和记录移动次数

均达到最小值：

，

。
所以，冒泡排序最好的时间复杂度为

。
　　若初始文件是反序的，需要进行

趟排序。每趟排序要进行

次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为

。
综上，因此冒泡排序总的平均时间复杂度为

。

算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。2015-10-21