java中的基本排序之冒泡排序和选择排序

爱被打了一巴掌 2022-08-09 01:48 122阅读 0赞

1、冒泡排序：相邻的两个元素进行比较，如果符合条件就换位。

需求：对指定的数组进行排序

功能：通过排序形成一个从小到大的排序结构返回类型为void

原理：第一圈：最值出现在最右端。

class BubbleSort
    {
    	public static void main (String[] args)
    	{
    	int[] array = {9,7,3,12,6,21,5,47,32,19,8};
    	printarray(array);
    	bubbleSort(array);
    	printarray(array);
    	}
    	public static void bubbleSort(int []a)
    	{
    	for(int i =0;i<a.length-1;i++)
    	{
    	    for(int j =0;j<a.length-i-1;j++)/*-i：让每一次比较的元素减少；
    						-1：避免角标越界*/
    	    {
    	    if(a[j]>a[j+1])
    		{
    		int t = a[j];
    		    a[j] =a[j+1];
    		    a[j+1] =t;
    		}
    	    }
    	}
    	
    	}
    	public static void printarray( int [] array)
    	{ 
    
    		for(int i =0;i<array.length;i++)
    		{
    		if(i!=array.length-1)
    		System.out.print(array[i]+","	);
    		else
    		System.out.println(array[i]	);
    		
    		}
    	}
    
    }

2、选择排序：内循环一次就将最大或最小的数找到。

需求：对指定的数组进行排序

功能：通过排序形成一个从小到大的排序结构返回类型为void

class SelectSort
    {
    	public static void main (String[] args)
    	{
    	int [] array = {5,9,4,8,12,7,19,25};
    	printarray(array);//排序前
    	selectSort(array);//排序
    	printarray(array);//排序后
    	}
    
    	public static void selectSort( int [] a)//选择排序
    	{ 
    	
    		for(int i =0;i<a.length-1;i++)
    		{
    		for(int j =i+1;j<a.length;j++)//内循环结束一次，最值出现在头角标的位置上
    		{	
    			if(a[i]>a[j])
    			{
    			int t =a[i];
    			    a[i] =a[j];
    			    a[j] = t;			
    			}
    		}	
    		}
    	}
    	public static void printarray( int [] b)//输出打印
    	{ 
    
    		for(int i =0;i<b.length;i++)
    		{
    		if(i!=b.length-1)
    		 System.out.print("array["+i+"]="+b[i]+","	);
    		else
    		  System.out.println("array["+i+"]="+b[i]	);
    		
    		}
    	}
    }

3、数组的查找操作

折半查找：可以提高效率，但是必须保证数组时有序的

功能：获取第一次出现在数组中的位置，如果返回-1，那代表该值不存在

class BiSearch
    {
    	public static void main (String[] args)
    	{
    	int[] array ={2,4,6,8,9,11,15,27，36};
    	int index=halfSearch(array,19);
    	System.out.println(index);
    	}
    	public static int halfSearch(int[] a,int key)
    	{
    	int min =0,max =a.length-1,mid;
    	
    	while(min<= max)
    	  {//进行折半查找  
    	    mid =(min+max)>>1; //mid的值会随着min和max值的改变而不断的改变
    	    if(key>a[mid])
    		min =mid+1;
    	    else  if(key<a[mid])
    		max =mid-1;
    	   // 当min==max时，即为mid时。
    	    else    
    		return mid;
    	   
    	  }//当查找的数不存在时
    	    return -1;
    	}
    }

4、数组的查找操作

折半查找：可以提高效率，但是必须保证数组是有序的

需求：有一个有序数组，想要将一个元素插入到该数组中，还要保证数组的有序性，即确定插入的位置

思路：通过折半查找确定插入的前后位置

class BiSearch
    {
    	public static void main (String[] args)
    	{
    	int[] array ={3,4,8,9,14,18,36};
    	int index =halfSearch(array,19);
    	System.out.println(index);
    	}
    	public static int halfSearch(int[] a,int key)
    	{
    	int min =0,max =a.length-1,mid;
    	while(min <= max)
    	  {  
    	  //mid的值会随着min和max值的改变而不断的改变,所以要写在内循环中
    	   mid =(min+max)/2;
    	    if(key>a[mid])
    		min =mid+1;
    	    else if(key<a[mid])
    		max =mid-1;
    	// 当min==max时，即为mid时	    
    	    else 
    		return mid;
    	  }//插入的位置
    	    return min;
    	}
    }