你的位置:首页 > Java教程

[Java教程]Java学习 (七)、数组,查找算法,二分查找法,冒泡排序,选择排序,插入排序


一、常用数组查找算法

工作原理:它又称为顺序查找,在一列给定的值中进行搜索,从一端的开始逐一检查每个元素,知道找到所需元素的过程。

例1:查找指定的数在数组中出现的位置,找到返回下标,找不到返回-1

 1 import java.util.Scanner; 2 public class LinearSearch{ 3   public static void main(String []argas) 4   { 5     int [] array={10,100,90,65,80,92}; 6     System.out.println("请输入要获取的数"); 7     Scanner input=new Scanner(System.in); 8     int number=input.nextInt(); 9     int index=-1;//找到数组中所在数的下标,找不到等于-110     for(int i=0;i<array.length;i++)11     {12       if(array[i]==number)13       {14         index=i+1;15         break;16       }17     }18     if(index!=-1)19     {20       System.out.println("找到该数字,在数组中的第"+index+"位置");21     }22     else23     {24       System.out.println("要查找的数字不存在");25     }26   }27 }

View Code

例2:求数组中的最大值,最小值

 1 public class LinearSearch{ 2   public static void main(String []argas) 3   { 4     int [] array={10,100,90,65,80,92}; 5     //求数组中的最大值,最小值 6     int max=array[0];//最大值 7     int min=array[0];//最小值 8     for(int i=1;i<array.length;i++) 9     {10       if(max<array[i])11       {12         max=array[i];13       }14       if(min>array[i])15       {16         min=array[i];17       }18     }19     System.out.println("该数组的最大值为"+max+",最小值为"+min);20   }21 }

View Code

二、二分查找法

工作原理:它又称为折半查找法,将数组中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将数组分成前、后两个子数组,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子数组,否则进一步查找后一子数组。重复以上过程,直到找到或找不到为止。

注:针对有序数组

 1 import java.util.Scanner; 2 public class LinearSearch{ 3   public static void main(String []argas) 4   { 5     int[] array2={1,2,3,4,5,10,15,18,19,22}; 6     System.out.println("请输入要获取的数"); 7     Scanner input=new Scanner(System.in); 8     int number=input.nextInt(); 9     int index=-1;//找到数组中所在数的下标,找不到等于-110     int start=0;//起始下标11     int end=array2.length-1;//终止下标12     int middle;13     while(start<=end)14     {15       //找到中间下标所对应的元素值16       middle=(start+end)/2;17       int number2=array2[middle];18       //假如要查找的那个数大于中间比较的那个数19       //去掉左边的数20       if(number>number2)21       {22         start=middle+1;23       }24       //保留左边的数,去掉右边的数25       else if(number<number2)26       {27         end=middle-1;28       }29       else30       {31         index=middle+1;32         break;33       }34     }35     if(index!=-1)36     {37       System.out.println("找到该数字,在数组中的第"+index+"位置");38     }39     else40     {41       System.out.println("要查找的数字不存在");42     }43     44   }45 }

View Code

三、冒泡排序法

工作原理:比较相邻的元素,如果第一个比第二个大,就交换它们两个。对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。最后的元素应该会是最大的数。针对除了最后一个元素以外所有的元素重复以上的步骤。直到没有任何一对数字需要比较。

 1 public class BubbleSort{ 2   public static void main(String []argas) 3   { 4     int[] array={80,53,12,90,35,22,65,45,82,33}; 5     //N个数比较的轮数为N-1次 6     for(int i=0;i<array.length-1;i++) 7     { 8       //每一轮比较的次数为N-1-i次 9       for(int j=0;j<array.length-i-1;j++)10       {11         //比较相邻的2个数,小靠前12         if(array[j]>array[j+1])13         {14           //两个数做交换,通过设置临时变量15           int temp=array[j];16           array[j]=array[j+1];17           array[j+1]=temp;18         }19       }20     }21     //把排好序的数组输出22     for(int i=0;i<array.length;i++)23     {24       System.out.print(array[i]+",");25     }26   }27 }

View Code

四、选择排序法

工作原理:首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

 1 public class SelectSort{ 2   public static void main(String []argas) 3   { 4     int[] array={80,53,12,90,35,22,65,45,82,33}; 5     int min=0;//保存最小元素值的下标 6     //N个数比较的轮数为N-1次 7     for(int i=0;i<array.length-1;i++) 8     { 9       min=i;10       //查找最小数在数组中的下标11       for(int j=i+1;j<array.length;j++)12       {13         if(array[min]>array[j])14         {15           min=j;//保存最小数的下标16         }17       }18       //如果第i个数位置不在i上,则进行交换19       if(i!=min)20       {21         int temp=array[i];22         array[i]=array[min];23         array[min]=temp;24       }25     }26     27     for(int i=0;i<array.length;i++)28     {29       System.out.print(array[i]+",");30     }31   }32 }

View Code

五、插入排序法

工作原理:它是通过构建有序序列,对于为排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

 1 public class InsertSort{ 2   public static void main(String []argas) 3   { 4     int[] array={80,53,12,90,35,22,65,45,82,33}; 5     for(int i=1;i<array.length;i++) 6     { 7       int temp=array[i]; 8       //把下标保存起来 9       int j=i;10       while(j>0&&temp<array[j-1])11       {12         //上面的数覆盖其下面的数13         array[j]=array[j-1];14         j--;15       }16       array[j]=temp;//插入数据17     }18     19     for(int i=0;i<array.length;i++)20     {21       System.out.print(array[i]+",");22     }23   }24 }

View Code