冒泡与选择排序

冒泡排序

算法描述：冒泡排序是一种交换排序，它的基本思想就是两两比较相邻的关键字，如果反序则交换，直到没有反序的记录为止

就像冒泡一样，第一次先把最大的选出来冒到最后，依次类推，从下个继续冒最大的

public static void bubbleSort(int a[]){
		int temp;  //临时变量，用于交换
		for(int i=a.length-1;i>0;i--) //外层循环，用于控制需要冒泡的个数
			for(int j=0;j<=i-1;j++) //内存循环
				if(a[j]>a[j+1]) //如果需要交换，则交换
				{
					temp=a[j+1];
					a[j+1]=a[j];
					a[j]=temp;
				}
	}

可以看出这个冒泡的实现是很简单的，但是效率上存在严重问题，比如有序数列2,1,3,4,5这个除了第一个，其余都已经是有序了，但是根据算法还是不断循环，比较增加了冗余，所以需要改进

public static void bubbleSort(int a[]){
	int temp;
	boolean flag=true; //用来作为标记
	for(int i=a.length-1;i>0&&flag;i--){ //如果flag为false，也就是已经有序了，退出
		flag=false;  //初始化为false
		for(int j=0;j<=i-1;j++)
			if(a[j]>a[j+1])
			{
				temp=a[j+1];
				a[j+1]=a[j];
				a[j]=temp;
				flag=true;  //如果有数据交换，则设为true
			}
}}

显然从效率上提高了许多，由内外循环次数可以得出其时间复杂度为o(n^2)

选择排序

算法描述：选择排序就是通过n-i此关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换

public static void ChooseSort(int[] a){
	int min,temp;  //分别为每一次循环的当前最小变量和临时变量
	for(int i=0;i<a.length;i++){
		 min=i; //初始化最小变量，为当前循环的第一个变量
	 for(int j=i+1;j<a.length;j++)
	 {
		 if(a[j]<a[i])  //找到比当前循环的最小变量小的记录，并记录下标
			 min=j;
	 }
	 if(min!=i) //如果有比当前最小变量小，则交换记录
	 {
		 temp=a[min];
		 a[min]=a[i];
		 a[i]=temp;			 
	 }
	}
}

可以看出它的时间复杂度仍然是O(n^2)

约瑟夫环的另一种解法

至于问题描述就不描述了，在之前的数据结构总结中已经有了这个问题的描述

public static void Count3Quit(){
		boolean[] arr=new boolean[500]; //初始化500个人围成圈
		 for(int i=0;i<arr.length;i++) //假设每个人值都为true
	      arr[i]=true;
		    int len=arr.length; //记录总人数
		    int index=0;  //记录每个人的索引
		    int count=0;  //记录数数变量，这里是数三退一
		     while(len>1)//直到只剩最后一个人为止
		     {
		    	 if(arr[index]==true) //人还在圈内
		    	 {
		    		 count++; //数数加一
		    		 if(count==3) //数到三时，退一个人
		    		 {
		    			 count=0; //计数重置为0
		    			  arr[index]=false; //该人退出
		    			   len--; //总人数减一
		    		 }
		    	 }
		    	 index++; //索引加一
		    	 if(index==arr.length)//索引超出人数长度，循环从0开始
		    		 index=0;
		     }
		     for(int i=0;i<arr.length;i++)//输出最后一个人
		    	 if(arr[i]==true)
		    		 System.out.println(i);
	}