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;//找到数组中所在数的下标,找不到等于-1
10         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         else
23         {
24             System.out.println("要查找的数字不存在");
25         }
26     }
27 }

例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 }

二、二分查找法

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

注:针对有序数组

 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;//找到数组中所在数的下标,找不到等于-1
10         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             else
30             {
31                 index=middle+1;
32                 break;
33             }
34         }
35         if(index!=-1)
36         {
37             System.out.println("找到该数字,在数组中的第"+index+"位置");
38         }
39         else
40         {
41             System.out.println("要查找的数字不存在");
42         }
43
44     }
45 }

三、冒泡排序法

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

 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 }

四、选择排序法

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

 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 }

五、插入排序法

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

 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 }

时间: 03-08

Java学习 (七)、数组,查找算法,二分查找法,冒泡排序,选择排序,插入排序的相关文章

算法 排序lowB三人组 冒泡排序 选择排序 插入排序

参考博客:基于python的七种经典排序算法   [经典排序算法][集锦]     经典排序算法及python实现 首先明确,算法的实质 是 列表排序.具体就是操作的列表,将无序列表变成有序列表! 一.排序的基本概念和分类 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作.排序算法,就是如何使得记录按照要求排列的方法. 排序的稳定性: 经过某种排序后,如果两个记录序号同等,且两者在原无序记录中的先后秩序依然保持不变,则称所使用的排序方法是稳定的,反之是不稳定

基本排序算法(冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序)

冒泡排序 public static void bubbleSort(int[] arr){ int lgn = arr.length; for (int i = 0; i < lgn - 1; i++) { for (int j = 0; j < lgn - 1 - i; j++) { if(arr[j] > arr[j + 1]){ int temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } } 选择排序 publ

javascript学习6-练习之3二分查找算法

二分查找算法,对数据进行查找并且显示位置. 核心思想:将所查找数据与查询数组中间的数进行比较,findVal<midVal,则在左边进行二分查找,否则在右边进行二分查找递归调用 具体代码如下: 1 //二分查找 2 var string2=[1,3,42,88,123,143]; 3 var leftIndex=0; 4 var rightIndex=5; 5 function binarySearch(string2,findVal,leftIndex,rightIndex) 6 { 7 if

算法—8.有序数组中的二分查找

1.具体算法 /** * 算法3.2 二分查找(基于有序数组) * Created by huazhou on 2015/11/29. */ public class BinarySearchST<Key extends Comparable<key>, Value> { private Key[] keys; private Value[] vals; private int N; public BinarySearchST(int capacity){ keys = (Key[

【Java_Base】常用查找算法:顺序查找、二分查找

顺序查找 从第一个元素开始顺序比较查找. 二分查找 二分查找前提条件: 已排序的数组中查找 二分查找的基本思想是: 首先确定该查找区间的中间点位置: int mid = (low+upper) / 2; 然后将待查找的值与中间点位置的值比较: 若相等,则查找成功并返回此位置. 若中间点位置值大于待查值,则新的查找区间是中间点位置的左边区域. 若中间点位置值小于待查值,则新的查找区间是中间点位置的右边区域. 下一次查找是针对新的查找区间进行的. 1 public class Search{ 2 p

动态数组,数组初始化,数组内存释放,向数组中添加一个元素,向数组中添加多个元素,数组打印,顺序查找,二分查找,查找数组并返回地址,冒泡排序,改变数组中某个元素的值,删除一个数值,删除所有,查找含有

 1定义接口: Num.h #ifndef_NUM_H_ #define_NUM_H_ #include<stdio.h> #include<stdlib.h> /************************************************************************/ /*数组的结构体类型                                                    */ /*******************

查找系列之简述顺序查找和二分查找

顺序查找和二分查找 一.顺序查找思想 1. 从表的一端开始扫描,顺序扫描线性表,依次扫描到的结点关键字与给定的值K相比较.如果当前扫描到的结点的关键字与给定的值K相等,则查找成功;若扫描结束后,仍未找到关键字与给定的值K相等,则查找失败; 2.顺序查找既适用于顺序存储结构,也适用于线性表的链式存储结构; 3.ASL= (n+1)/2为其平均查找长度 4.优点:算法简单,对存储结构形式没有要求 缺点:浪费空间,当长度非常大是效率低 5.算法描述: /** *顺序查找 *@param int a[]

顺序查找和二分查找

1.使用PHP描述顺序查找和二分查找(也叫做折半查找)算法,顺序查找必须考虑效率,对象可以是一个有序数组[转] 2.顺序查找 <?php//$n为待查找的数组元素的个数,$k为待查找的元素function seq_sch($array, $n, $k){ $array[$n] = $k; for($i=0; $i<$n; $i++){ if($array[$i]==$k){ return true;break; } } if ($i<$n) //判断是否到数组的末尾{ return $i

java学习之数组(二)

学编程吧java数组学习(二)发布了,欢迎大家通过xuebiancheng8.com来访问. 下面接着来分析数组,前面分析了什么是数组,为什么要用数组,下面来分析下如何使用数组 数组和其他数据类型一样,使用前要先定义.如下 int a[];这样就声明了一个数组 a = new int[10];然后为这个数组申请10个大小的空间 a[0] = 1; a[1] = 2; ....等等来为数组 赋值,为数组赋值完成后就可以通过下标来访问数组 当然数组在定义的时候也可以讲上面操作合并即 int a []

java学习之数组(一)

学编程吧java学习之数组发布了,欢迎大家通过xuebiancheng8.com来访问. 下面来分析下java中的数组. 什么是数组呢,为什么要用数组呢,加入现在需要统计一个班的考试成绩,这个班有30个学生,怎么办呢,如果不用数组,那么就得定义30个变量来保存30名同学的成绩,这样很明显对程序员来说是非常痛苦呢,光30个变量就得定义半天,而且又都不好记,容易记混了,那怎么办呢,这个时候就可以用数组,数组故名思议就是一组数的几个就叫数组,这这一组数使用同一个变量,只要一个变量就可以保存这30个同学