冒泡、选择、插入、二分排序算法

拼搏现实的明天。 2023-10-17 14:26 2阅读 0赞

冒泡排序:

首先,冒泡排序又称起泡排序我这里总结了排序两种冒泡排序一种是普通的冒泡排序,一种是优化后冒泡,冒泡排序就是拿第一个数其他所有的数去比较,经过一趟比较把这组数据最大的数据找出来第一次总共要比较(n-1趟),接着又从第一个数开始找第二大的数(n-2趟),以此类推........,

附代码如下:

public void swap(int[]a, int i, int j){
    		int temp = a[i];
    		a[i]=a[j];
    		a[j]=temp;
    	}
    	public void print(int a[]){
    		for(int x:a){
    			System.out.print(x+" ");
    		}
    		System.out.println();
    	}
            1.1普通冒泡
    	@Test
    	public void bubbleSort(){
    		int a[]={21,25,49,25,16,8};
    		print(a);
    		
    		for(int i=0;i<a.length-1;i++){//趟数:n-1
    			//第i趟
    			//每一趟产生一个最大数放在最后(冒泡): 让第j 和 j+1 个数进行比较，违反需求则交换。j:0~n-i-1
    			for(int j=0; j<a.length-i-1; j++){
    				if(a[j]>a[j+1]){
    					swap(a,j,j+1);
    				}
    			}
    		}
    		print(a);
    	}

所谓优化后的冒泡排序就是,在排序的过程中,发现某一趟的数据都没有交换(实际是已经排序完成了)后面就不需要在排序了

附代码如下:

@Test
    	public void bubbleSort2(){
    		int a[]={21,25,49,25,16,8};
    		print(a);
    		
    		for(int i=0;i<a.length-1;i++){//趟数:n-1
    			boolean boo = false;
    			for(int j=0; j<a.length-i-1; j++){
    				if(a[j]>a[j+1]){
    					swap(a,j,j+1);
    					boo=true;
    				}
    			}
    			if(!boo){
    				break;
    			}
    		}
    		print(a);
    	}

选择排序:

这里选择排序我也总结的两种排序算法,一种是普通的选择排序,一种就是有优化后的选择排序,选择排序的思路也比简单,就是每一个数都与其后面的数作比较,这里我就用大家"换手机"为例;

普通的选择排序:

附代码如下:

@Test
       public void selectSort(){
    	   int a[]={21,25,49,25,16,8,-1,0,23,44};
    	   print(a);
    	   
    	   for(int i=0;i<a.length-1; i++){//趟数:第i个排
    		   //第i趟:让第i个人依次找他后面的每一个人，如果后者的手机更烂(就把后者的序号k记下，下次用a[k]和后续的人比)，依此类推直到最后一个同学
    		   int k=i;
    		   for(int j=i+1;j<a.length;j++){
    			   if(a[k]>a[j]){
    				   k=j;//记下当前最小值的序号
    			   }
    		   }
    		   if(i!=k){
    			   swap(a,i,k);
    		   }
    	   }
    	   print(a);
       }

优化后选择排序:

附代码如下:

@Test
       public void selectSort0(){
    	   int a[]={21,25,49,25,16,8,-1,0,23,44};
    	   print(a);
    	   
    	   for(int i=0;i<a.length-1; i++){//趟数:第i个排
    		   //第i趟:让第i个人依次找他后面的每一个人，如果后者的手机更烂就跟他换，依此类推直到最后一个同学
    		   for(int j=i+1;j<a.length;j++){
    			   if(a[i]>a[j]){
    				   swap(a,i,j);//换手机: 把当前最小值的元素和a[i]交换
    			   }
    		   }
    	   }
    	   print(a);
       }

插入排序:

插入排序算法就是依次把每个元素拿来插入到有序序列中( 刚开始，第1个元素不要动，可看作已经有序。因此排的时候只考虑第2~n个数,从后插入,一旦前面的数比待插入的数大,就把前面的数往后移动一位.这里我把二分和插入的排序算法结合起来了!

普通的的插入排序:

附代码如下:

@Test
       public void insertSort(){
    	   int a[]={21,25,49,25,16,8,-1,0,23,44};
    	   print(a);	   
    	   //依次把每个元素拿来插入到有序序列中( 刚开始，第1个元素不要动，可看作已经有序。因此排的时候只考虑第2~n个数
    	   for(int i=0;i<a.length-1;i++){
    		   //待插入的数
    		   int temp = a[i+1];		   
    		   //下面这段决定temp坐在哪个位置(j+1)  同时 让所有比temp大的数往后挪一个位置
    		   int j=i;
    		   while(a[j]>temp){//如果有序序列中"第j位置的数" 比 "temp(待插入的数)" 大，则把a[j]往后挪一个位置
    			   a[j+1]=a[j];
    			   j--;
    			   if(j<0){
    				   break;
    			   }
    		   }		   
    		   //出了该循环,说明temp比a[j]大或者到达左边界(j为-1)。此时temp就坐在a[j+1]		   
    		   a[j+1]=temp;//坐在j的后面
    	   }
    	   print(a);
       }

★二分一定要有序， 如果有序要记得考虑二分

二分法就是把数据分为两段,首先待插入的数与有序中间位置的数比较,则就可以减少一半的比较量,这里我把插入排序算法和二分排序算法结合起来了

附代码如下:

@Test
       public void insertSort2(){
    	   int a[]={21,25,49,25,16,8,-1,0,23,44};
    	   print(a);	   
    	   //依次把每个元素拿来插入到有序序列中( 刚开始，第1个元素不要动，可看作已经有序。因此排的时候只考虑第2~n个数
    	   for(int i=0;i<a.length-1;i++){
    		   //待插入的数
    		   int temp = a[i+1];		   
    		   //用二分来找出将要插入的位置:high+1
    		   int low = 0;
    		   int high = i;
    		   int mid;//中间位置
    		   while(low<=high){
    			   mid = (low+high)/2;
    			   if(a[mid]>temp){//temp落在左区
    				   high = mid-1;
    			   }else{//temp落在右区
    				   low = mid+1;
    			   }
    		   }//出循环,low是错的--不应该跑到high的后面		   
    		   //把该位置(high+1)腾出来，即把high+1及其后面的元素依次往后挪一个位置
    		   //注意，要倒着移动
    		   for(int j=i;j>high;j--){
    			  a[j+1]=a[j]; 
    		   }		  
    		   //出了该循环,说明temp比a[j]大或者到达左边界(j为-1)。此时temp就插入到a[j+1]
    		   a[high+1]=temp;//放在j的后面
    	   }
    	   print(a);
       }