常见算法（2）

1.冒泡排序

定义：相邻的数据两两比较，小的放前面，大的放后面。

public class test {
		public static void main(String [] arg)   {
		  int [] arr= {2,4,5,3,6,1};
		  //冒泡排序，排序次数arr.length-1
		  for(int i=0;i<arr.length-1;i++) {
			  for(int j=0;j<arr.length-1;j++) {//相邻元素两两交换
				  if(arr[j]>arr[j+1]) {
					  int tem=arr[j];
					  arr[j]=arr[j+1];
					  arr[j+1]=tem;
				  }
			  }
		  }
		  //打印
		  for(int i=0;i<arr.length;i++) {
			  System.out.print(arr[i]+" ");
		  }
		  
		}
}

2.选择排序

定义：从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较，小的放前面，大的放后面。

public class test {
		public static void main(String [] arg)   {
		  int [] arr= {2,4,5,3,6,1};
		  //选择排序，排序次数arr.length-1
		  for(int i=0;i<arr.length-1;i++) {//外循环，比较次数
			  for(int j=i+1;j<arr.length;j++) {//内循环，每一轮要干的事情
				  if(arr[i]>arr[j]) {
					  int tem=arr[i];
					  arr[i]=arr[j];
					  arr[j]=tem;
				  }
			  }
		  }
		  //打印
		  for(int i=0;i<arr.length;i++) {
			  System.out.print(arr[i]+" ");
		  }
		  
		}
}

3.插入排序

定义：将0索引的元素到N索引的元素看作是有序的，把N+1索引的元素到最后一个当成无序的，遍历无序的数据，将遍历到的元素插入到有序序列中适当位置，如遇相同数据，插在后面。

分析：先找无序开始的下标，利用for循环遍历无序数组，利用while循环交换数据。

public class test {
		public static void main(String [] arg)   {
		 //插入排序
			int []arr= {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
			//先寻找无序是从哪一个下标开始的
			int index=-1;
			for(int i=0;i<arr.length;i++) {
				if(arr[i]>arr[i+1]) {
					index=i+1;//无序开始的下标
					break;
				}
			}
			//对无序数组进行遍历，排序
			for(int i=index;i<arr.length;i++) {
				int j=i;//定义一个新变量，将i赋给
				while(j>0&&arr[j]<arr[j-1]) {
					int tem=arr[j];
					arr[j]=arr[j-1];
					arr[j-1]=tem;
					j--;
				}
			}
			for(int i=0;i<arr.length;i++) {
				System.out.print(arr[i]+" ");
			}
			}
}

递归算法

定义：方法中调用方法本身的现象。

小练习：用递归算法求1~100的和。

分析：1~100的和可以拆成100+（1~99）的和

1~99的和可以拆成99+（1~98）的和

1~98的和可以拆成98+（1~97）的和.....等等

public class test {
		public static void main(String [] arg)   {
		 //1~100的和
			System.out.println(getsum(100));
			}
		public static int getsum(int number) {
			if(number==1) {
				return 1;
			}
			return number+getsum(number-1);
		}
}

4.快速排序

第一轮：把0索引数字作为基准数，确定基准数在数组中的正确位置。比基准数小的全部在左边，比基准数大的全部在右边。

方法：定义两个变量：start，end；利用while循环先遍历end再遍历start，找到比基准数小、比基准数大停止，然后交换start和end位置，并循环。直至两个处于同一位置，该位置将基准数存入。再将此基准数的左右两边，再次调用此方法。

public class test {
		public static void main(String [] arg)   {
			//快速排序
		 int[] arr= {6,1,2,7,9,3,4,5,10,8 };
		 quick(arr,0,arr.length-1);
		 for(int i=0;i<arr.length;i++) {
			 System.out.print(arr[i]+" ");
		 }
		}
		public static void quick(int [] arr,int i,int j) {//数组，i为起始，j为结束
			//定义查找范围
			int start=i;
			int end=j;
			if(start>end) {//递归出口
				return;
			}
			//记录基准数
			int basenumber=arr[i];
			//利用循环交换数据
			while(start!=end) {
				//判断end什么时候停止
				while(true) {
					if(end<=start||arr[end]<basenumber) {
						break;
					}
					end--;
				}
				//start
				while(true) {
					if(end<=start||arr[start]>basenumber) {
						break;
					}
					start++;
				}
				//交换start和end
				int tem=arr[start];
				arr[start]=arr[end];
				arr[end]=tem;
			}
			//交换基准数和start或end的位置
			int tem=arr[i];
			arr[i]=arr[end];
			arr[end]=tem;
			
			//再对左边和右边进行调用
			quick(arr,i,start-1);
			quick(arr,start+1,j);
			
		}
}