查找算法
public class day11 {
public static void main(String[] args) {
//基本查找 / 顺序差宅
//核心:
//从0索引开始挨个往后查找
//需求:定义一个方法利用基本查找 查询某个元素是否存在
//数据如下:{131,127,147,81,103,23,7,79}
int[] arr={131,127,147,81,103,23,7,79};
int number=81;
System.out.println(basicSearch(arr, number));
}
public static boolean basicSearch(int[] arr,int number){
for (int i = 0; i < arr.length; i++) {
if(arr[i]==number){
return true;
}
}
return false;
}
}import java.util.ArrayList;
public class day11 {
public static void main(String[] args) {
//需求:定义一个方法利用基本查找 查询某个元素在数组中的索引
//要求:需要考虑数组中元素有重复的可能性
int[] arr={131,127,147,81,103,23,7,79,81};
//要返回3 8
int number=81;
System.out.println(basicSearch(arr, number));//[3, 8]
}
//心得:如果我们要返回多个数据的话 可以把这些数据放到数组或者集合中.
public static ArrayList basicSearch(int[] arr,int number){
ArrayList<Integer>list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if(arr[i]==number){
list.add(i);
}
}
return list;
}
}
public class day11 {
public static void main(String[] args) {
int[] arr={7,23,79,81,103,127,131,147};
System.out.println(binaryResearch(arr,147));
}
public static int binaryResearch(int[] arr,int k){
int max =arr.length-1;
int min =0;
while(true){
if(min>max){
return -1;
}
int mid =(min+max)/2;
if(arr[mid]>k){
max=mid-1;
}else if(arr[mid]<k){
min=mid+1;
}else{
return mid;
}
}
}
}
现实生活中不可能都这样 大部分都是一些有顺序一些无顺序
public class day11 {
public static void main(String[] args) {
int[] arr = {16, 5, 9, 12, 21, 18,
32, 23, 37, 26, 45, 34,
50, 48, 61, 52, 73, 66};
//1.要把数据进行分块
//要分几块 18开根号 4.24块
//18/4=4.5
//创建三个块的对象
Block b1 =new Block(21,0,5);
Block b2 =new Block(45,6,11);
Block b3 =new Block(73,12,17);
//定义数组来管理三个块的对象(索引表)
Block[] blockArr={b1,b2,b3};
//定义一个变量用来记录要查找的元素
int number=37;
//调用方法:传递索引表,数组,要查找的元素
int index =getIndex(blockArr,arr,number);
//打印一下
System.out.println(index);
}
//利用分块查找的原理 查询number的索引
//1.确定number在索引标的位置
private static int getIndex(Block[] blockArr,int[] arr,int number){
int indexBlock = findIndexBlock(blockArr,number);
if(indexBlock==-1){
//表示number不在数组当中的
return -1;
}
//获取这一块的起始索引和结束索引
int startIndex =blockArr[indexBlock].getStartIndex();
int endIndex =blockArr[indexBlock].getEndIndex();
//遍历
for(int i=startIndex;i<=endIndex;i++){
if(arr[i]==number){
return i;
}
}
return -1;
}
//定义一个方法 用来确定number在那一块中
public static int findIndexBlock(Block[] blockArr,int number){
// Block b1 =new Block(21,0,5);-----0
// Block b2 =new Block(45,6,11);----1
// Block b3 =new Block(73,12,17);---2
//从0索引开始遍历blockArr,如果number小于max,那么就表示number就是在这一块当中的
for (int i = 0; i < blockArr.length; i++) {
if(number<=blockArr[i].getMax()){
return i;
}
}
return -1;
}
}
class Block {
private int max;//最大值
private int startIndex;//起始索引
private int endIndex;//结束索引
public Block() {
}
public Block(int max, int startIndex, int endIndex) {
this.max = max;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
/**
* 获取
* @return max
*/
public int getMax() {
return max;
}
/**
* 设置
* @param max
*/
public void setMax(int max) {
this.max = max;
}
/**
* 获取
* @return startIndex
*/
public int getStartIndex() {
return startIndex;
}
/**
* 设置
* @param startIndex
*/
public void setStartIndex(int startIndex) {
this.startIndex = startIndex;
}
/**
* 获取
* @return endIndex
*/
public int getEndIndex() {
return endIndex;
}
/**
* 设置
* @param endIndex
*/
public void setEndIndex(int endIndex) {
this.endIndex = endIndex;
}
public String toString() {
return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
}
}
排序算法
public class day11 {
public static void main(String[] args) {
//冒泡排序
//核心思想:
//相邻的两个元素两两比较 大的放右边,小的放左边
//第一轮比较完毕之后,最大值就已经确定了,第二轮可以减少循环一次 后面一次类推
//如果数组中有n个数,总共只需要执行n-1次循环就可以了
//1.定义数组
//2.利用冒泡排序将数组中的数据变成12345
//第一轮:
//结束之后,最大值在数组的最右边 ....5
int[] arr={2,4,5,3,1};
//i表示数组中每个元素的索引 0 1 2 3 4
for(int i=0;i<arr.length-1;i++){//0 1 2 3
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}//-1:为了防止索引越界
//-i:提升效率 每一轮执行的次数应该比上一轮少一次
}
}
printArr(arr);
}
public static void printArr(int[] arr){
for(int k=0;k<arr.length;k++){
System.out.print(arr[k]+" ");
}
System.out.println();
}
}
public class day11 {
public static void main(String[] args) {
//选择排序
// int[] arr={2,4,5,3,1};
// for (int i = 0+1; i < arr.length; i++) {
// if(arr[0]>arr[i]){
// int temp=arr[0];
// arr[0]=arr[i];
// arr[i]=temp;
// }
// }
//最终代码
int[] arr={2,4,5,3,1};
//外循环:几轮
//i:表示这一轮中 我拿着那个索引上的数据跟后面的数据进行比较并交换
for (int i = 0; i < arr.length-1; i++) {
//内循环:每一轮干什么事情
//拿着i跟i后面的数据进行交换
for (int j = i+1; j < arr.length; j++) {
if(arr[i]>arr[j]){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
printArr(arr);
}
public static void printArr(int[] arr){
for(int k=0;k<arr.length;k++){
System.out.print(arr[k]+" ");
}
System.out.println();
}
}
将无序插入有序
public class day11 {
public static void main(String[] args) {
//插入排序
int[] arr={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
//1.找到无序的那组数据
int startIndex=-1;
for (int i = 0; i < arr.length; i++) {
if(arr[i]>arr[i+1]){
//System.out.println(i+1);
startIndex=i+1;
break;
}
}
//2.遍历从startIndex开始到最后一个元素,依次得到无序的那一组数据中的每一个元素
for (int i = startIndex; i < arr.length; i++) {
//System.out.println(arr[i]);
//问题:如何把遍历到的数据,插入到前面有序的这一组当中
//记录当前要插入数据的索引
int j=i;
while(j>0&&arr[j]<arr[j-1]){
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
j--;
}
//修改这个索引
}
printArr(arr);
}
public static void printArr(int[] arr){
for(int k=0;k<arr.length;k++){
System.out.print(arr[k]+" ");
}
System.out.println();
}
}
public class day11 {
public static void main(String[] args) {
//递归求和
//大问题->小问题
//1~100=100+1~99
System.out.println(getSum(100));//5050
}
public static int getSum(int number){
if(number==1){
return 1;
}
return number+getSum(number-1);
}
}
public class day11 {
public static void main(String[] args) {
System.out.println(FactorialRecursion(5));
}
public static int FactorialRecursion(int number){
if(number==1){
return 1;
}
//方法再调用时 参数必须更靠近出口
return number*FactorialRecursion(number-1);
}
}
public class test {
public static void main(String[] args) {
int[] arr={6,1,2,7,9,3,4,5,10,8};
quickSort(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
public static void quickSort(int[] arr,int i,int j){
//记录两个变量记录查找的范围
int start=i;
int end=j;
if(start>end){
return;//递归的出口
}
//记录基准数
int baseNumber=arr[i];
//利用循环找到要交换的数字
while(start!=end){
//利用end，从后往前开始找，找比基准数小的数字
while(true){
if(end<=start||arr[end]<baseNumber){
break;
}
end--;
}
//利用start，从前往后找 ，找比基准数打的数字
while(true){
if(end<=start||arr[start]>baseNumber){
break;
}
start++;
}
//把end和start指向的元素进行交换
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
/*
* 参数一：要排序的数组
* 参数二：要排序数组的起始索引
* 参数三：要排序数组的结束索引
* */
//当start和end指向了同一个元素 那么上面的循环就会结束
//表示以及找到了基准数在数组中应存入的位置
//基准数归位
//就算拿着这个范围中的第一个元素 根start指向的元素进行交换
int temp=arr[i];
arr[i]=arr[start];
arr[start]=temp;
//确定6左边的范围,重复刚刚的事情
quickSort(arr,i,start-1);
//右边
quickSort(arr,start+1,j);
}
}
不能先移动start 不然会造成下面的结果
Arrays
数组的工具类
import java.util.Arrays;
public class test {
public static void main(String[] args) {
//toString:将数组变成字符串
System.out.println("----------toString-----------");
int[] arr={1,2,3,4,5,6,7,8,9,10};
System.out.println(Arrays.toString(arr));
//binarySearch:二分查找查找元素
//细节1:二分查找的前提 数组中的元素必须是有序的 数组中的元素必须是升序的
//细节2:如果要查找的元素是存在的 那么返回真实的索引
//但是,如果要查找的元素是不存在的,返回的是-插入点-1
//为什么-1?
//解释:如果此时要查找的数字是0 如果返回-插入点,就会出现问题 因为按照上面的规则返回值是-插入点 也就是-0 -0也是0
//为了避免这样的情况 Java就减一
System.out.println("----------binarySearch--------");
System.out.println(Arrays.binarySearch(arr, 10));
System.out.println(Arrays.binarySearch(arr, 2));
System.out.println(Arrays.binarySearch(arr, 20));//-11
//copyOf:拷贝数组
//参数一:老数组
//参数二:新数组的长度
//方法的底层会根据第二个参数来创建新的数组
//新数组小于 部分拷贝
//新数组 大于 补上默认初始化值0
System.out.println("---------copyOf-------------");
int[] newArr1 =Arrays.copyOf(arr,20);
System.out.println(Arrays.toString(newArr1));
//copyOfRange:拷贝数组(指定范围)
//细节:包头不包尾
System.out.println("----------copyOfRange---------");
int[] newArr2=Arrays.copyOfRange(arr,0,9);
System.out.println(Arrays.toString(newArr2));
//fill:填充数组
System.out.println("------------fill---------------");
Arrays.fill(arr,100);
System.out.println(Arrays.toString(arr));
//sort:排序 默认情况下,给基本数据类型进行升序排序
//底层使用的是快速排序.
System.out.println("----------sort------------");
int[] arr2={10,2,3,5,6,1,7,8,4,9};
Arrays.sort(arr2);
System.out.println(Arrays.toString(arr2));
}
}
import java.util.Arrays;
import java.util.Comparator;
public class test {
public static void main(String[] args) {
/*public static void sort(数组,排列规则) 按照指定的规则排序
*
* 参数一:要排序的数组
* 参数二:排序的规则
* 细节:
* 只能给引用数据类型的数组进行排序
* 如果数组是基本数据类型的 ,需要变成其对于的包装类
* */
Integer[] arr={2,3,1,5,6,7,8,4,9};
//第二个参数是一个接口 所以我们在调用方法的时候 需要传递这个接口的实现类对象 作为排序的规则
//但是这个实现类 只要使用一次 所以就没有必要单独去写一个类 直接才去匿名内部类的方式就可以了
//底层原理:
//利用插入排序+二分查找到方式进行排序的
//默认把0索引的数据当做是有序的序列,1索引到最后当做无序序列
//遍历无序的序列得到里面的每一个元素 假设当前遍历得到的元素是A元素
//把A往有序序列中进行插入,在插入的时候,是利用二分查找确定A元素的插入点
//拿着A元素 跟插入点的元素进行比较 比较的规则就是compare的方法的方法体
//如果方法的返回值是负数,拿着A继续跟前面的数据进行比较
//如果方法的返回值是正数,拿着A继续跟后面的数据进行比较
//如果方法的返回值是0,也拿着A跟后面的数据进行比较
//直到能够确定A的最终位置为止
//compare方法的心事参数:
//参数1 o1: 表示在无序序列中 遍历得到的每一个元素
//参数2 o2: 有序序列中的元素
//返回值:
//负数:表示当前要插入的元素是小的 放在前面
//正数:表示当前要插入的元素是大的 放在后面
//0:表示当前要插入的元素跟现在的元素比是一样的 也会放在后面
//简单理解:
//o1-o2:升序排列
//o2-o1:降序排列
Arrays.sort(arr, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
System.out.println("--------------");
System.out.println("o1:"+o1);
System.out.println("o2:"+o2);
return o1-o2;
}
});
System.out.println(Arrays.toString(arr));
}
}Lambda表达式
import java.util.Arrays;
public class test {
public static void main(String[] args) {
//初始Lambda表达式 - 简化匿名内部类的书写
Integer[] arr={2,3,1,5,6,7,8,4,9};
// Arrays.sort(arr, new Comparator<Integer>() {
// @Override
// public int compare(Integer o1, Integer o2) {
// return o1-o2;
// }
// });
Arrays.sort(arr, (Integer o1, Integer o2)-> {
return o1-o2;
}
);
System.out.println(Arrays.toString(arr));
}
}
public class test {
public static void main(String[] args) {
//1.利用匿名内部类的形式去调用下面的的方法
//调用一个方法的时候,如果方法的形参是一个接口,那么我们要传递这个接口的实现类对象
//如果实现类对象只要用到一次,就可以用匿名内部类的形式进行书写
// method(new Swim() {
// @Override
// public void swimming() {
// System.out.println("正在游泳");
// }
// });
//2.利用lambda表达式进行改写
method(
()->{
System.out.println("正在游泳");
}
);
}
public static void method(Swim s){
s.swimming();
}
}
@FunctionalInterface
interface Swim{
public abstract void swimming();
}
import java.util.Arrays;
import java.util.Comparator;
public class test {
public static void main(String[] args) {
Integer[] arr={2,3,1,5,6,7,8,4,9};
Arrays.sort(arr, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1-o2;
}
});
//Lambda完整格式
Arrays.sort(arr,(Integer o1, Integer o2)-> {
return o1-o2;
}
);
//Lambda省略写法
Arrays.sort(arr,( o1, o2)-> o1-o2);
System.out.println(Arrays.toString(arr));
}
}
import java.util.Arrays;
public class test {
public static void main(String[] args) {
String[] arr={"a","aaaa","aaa","aa"};
//如果以后我们要把数组中的数据按照指定的方式进行排列 就需要用到sort方法,而且要制定排序的规则
// Arrays.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
//按照字符串长度进行排序
return o1.length()-o2.length();
}
});
// Arrays.sort(arr,(String o1, String o2)-> {
// //按照字符串长度进行排序
//
// return o1.length()-o2.length();
// }
// );
Arrays.sort(arr,( o1, o2)->o1.length()-o2.length());
//打印数组
System.out.println(Arrays.toString(arr));
}
}
import java.util.Arrays;
public class test {
public static void main(String[] args) {
//前置知识 用compareTo来比较两个字符串
// String s1="a";//97
// String s2="b";//98
// int i=s1.compareTo(s2);
// System.out.println(i);//-1 s1<s2
//1.创建三个女朋友的对象
GirlFriend gf1 =new GirlFriend("xiaoshishi",18,1.67);
GirlFriend gf2 =new GirlFriend("xiaodandan",19,1.72);
GirlFriend gf3 =new GirlFriend("xiaohuihui",19,1.78);
//2.定义数组存储女朋友信息
GirlFriend[] arr={gf1,gf2,gf3};
//3.利用Arrays中的sort方法进行排序
//匿名内部类 Lambda
// Arrays.sort(arr, new Comparator<GirlFriend>() {
// @Override
// public int compare(GirlFriend o1, GirlFriend o2) {
// double temp = o1.getAge() - o2.getAge();
// temp = temp==0?o1.getHeight()-o2.getHeight():temp;
// temp = temp==0?o1.getName().compareTo(o2.getName()):temp;
// if(temp>0){
// return 1;
// }else if(temp<0){
// return -1;
// }else{
// return 0;
// }
//
// }
// });
Arrays.sort(arr, (o1,o2)-> {
double temp = o1.getAge() - o2.getAge();
temp = temp==0?o1.getHeight()-o2.getHeight():temp;
temp = temp==0?o1.getName().compareTo(o2.getName()):temp;
if(temp>0){
return 1;
}else if(temp<0){
return -1;
}else{
return 0;
}
}
);
//展示一下数组中的内容
System.out.println(Arrays.toString(arr));
}
}public class GirlFriend {
private String name;
private int age;
private double height;
public GirlFriend() {
}
public GirlFriend(String name, int age, double height) {
this.name = name;
this.age = age;
this.height = height;
}
/**
* 获取
* @return name
*/
public String getName() {
return name;
}
/**
* 设置
* @param name
*/
public void setName(String name) {
this.name = name;
}
/**
* 获取
* @return age
*/
public int getAge() {
return age;
}
/**
* 设置
* @param age
*/
public void setAge(int age) {
this.age = age;
}
/**
* 获取
* @return height
*/
public double getHeight() {
return height;
}
/**
* 设置
* @param height
*/
public void setHeight(double height) {
this.height = height;
}
public String toString() {
return "GirlFriend{name = " + name + ", age = " + age + ", height = " + height + "}";
}
} 
public class test {
public static void main(String[] args) {
// //方法一:
// //1.创建一个长度为12的数组
// int[] arr=new int[12];
// //2.手动给0索引和1索引的数据进行赋值
// arr[0]=1;
// arr[1]=1;
//
// //3.利用循环给剩余的数据进行赋值
// for(int i=2;i<arr.length;i++){
// arr[i]=arr[i-1]+arr[i-2];
// }
// //1 1 2 3 5 8 13...
//
// //获取最大索引上的数据即可
// System.out.println(arr[11]);
//方法二:
//1.递归出口
//2.递归规律
System.out.println(getSum(12));
}
public static int getSum(int month){
if(month==1||month==2){
return 1;
}
return getSum(month-1)+getSum(month-2);
}
}
public class test {
public static void main(String[] args) {
/*day10:1
day9:(day10+1)*2 =4
day8:(day9+1)*2 =10
* */
System.out.println(getCount(1));
}
public static int getCount(int day){
if(day<=0||day>=11){
System.out.println("当前时间错误");
return -1;
}
if(day==10){
return 1;
}
return (getCount(day+1)+1)*2;
}
}
