JavaSE(13) - 常见算法 algorithm
查找算法 Search
基本查找 BasicSearch
package algorithm.search;
/*BasicSearch
1.用基本查找,查找某个元素在数组中的索引(不考虑重复元素)
2.用基本查找,查找某个元素在数组中的索引(考虑重复元素)*/
public class BasicSearch {
public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 3, 3};
int number = 2;
int[] result = getIndexArray(arr, number);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
//基本查找,(不考虑重复元素)
public static int getIndex(int[] arr, int number) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == number) {
return i;
}
}
return -1;
}
//基本查找,(考虑重复元素)
public static int[] getIndexArray(int[] arr, int number) {
//如果没有找到该元素,作出提示并返回空数组
if (getElements(arr,number) == 0){
System.out.println("没有此数据");
return new int [0];
}
//创建结果数组,长度为:数组中有几个查找到的元素
int[] indexArr = new int[getElements(arr, number)];
//创建数组的索引
int index = 0;
//遍历源数组
for (int i = 0; i < arr.length; i++) {
//如果找到这个元素, 就把这个元素的索引赋值给结果数组
if (arr[i] == number) {
indexArr[index] = i;
//赋值后,结果数组的索引加一
index++;
}
}
return indexArr;
}
//数组中有几个查找到的相同的元素,就是新数组的长度
public static int getElements(int[] arr, int number) {
//找到多少个元素
int ele = 0;
//遍历数组
for (int i = 0; i < arr.length; i++) {
//找到一个元素,就把变量加一
if (arr[i] == number) {
ele++;
}
}
return ele;
}
}
二分法查找 BinarySearch
- 二分查找的优势？
提高查找效率
- 二分查找的前提条件？
数据必须是有序的
如果数据是乱的，先排序再用二分查找得到的索引, 没有实际意义，只能确定当前数字在数组中是否存在，因为排序之后数字的位置就可能发生变化了
- 二分查找的过程
min和max表示当前要查找的范围
mid是在min和max中间的
**如果要查找的元素在mid的左边，缩小范围时，min不变，max等于mid减1 **
如果要查找的元素在mid的右边，缩小范围时，max不变，min等于mid加1
public static int getIndex(int[] arr, int element) {
//创建两个变量 表示要查找的范围
int min = 0;
int max = arr.length - 1;
//循环查找
while (true) {
//结束条件:min跑到max的右边就是没有此元素,返回-1
if (min > max){
return -1;
}
//找数据
//得到中间值
int mid = (min + max) / 2;
//如果mid和element相同就返回索引
if (element == arr[mid]) {
return mid;
//如果element大于mid,说明元素在mid的右边,就把最小值min变成mid加一
} else if (element > arr[mid]) {
min = mid + 1;
//如果ele小于mid,就是在mid左边,就max变成mid减一.
} else max = mid - 1;
}
}
分块查找 BlockSearch
public class blockSearch {
public static void main(String[] args) {
//要分成几块 : 一般要分成元素个数的开根号块
int[] arr = {3, 6, 5, //0-2
33, 31, 36, //3-5
77, 66, 99}; //6-8
//创建block对象
block b1 = new block(6, 0, 2);
block b2 = new block(36, 3, 5);
block b3 = new block(99, 6, 8);
//创建block对象数组来管理三个块--<<索引表>>
block[] blockArr = {b1, b2, b3};
//调用块查找方法
System.out.println(getIndex(blockArr, arr, 99));
}
//块查找方法 参数:索引表, 数组, 要找的元素
public static int getIndex(block[] blockArr, int[] arr, int number) {
//调用方法,找到要找的元素在哪个块里
int index = getBlockIndex(blockArr, number);
//表示number不在数组中
if (index == -1) {
return -1;
}
//获得这一块中的起始索引和结束索引,再遍历
int start = blockArr[index].getStartIndex();
int end = blockArr[index].getEndIndex();
//在数组里查找
for (int i = start; i <= end; i++) {
if (number == arr[i]) {
return i;
}
}
return -1;
}
//找到要找的元素在哪个块里
public static int getBlockIndex(block[] arr, int number) {
//从0索引开始遍历blockArr,如果number小于max,那么就表示number在哪个块里.
for (int i = 0; i < arr.length; i++) {
int max = arr[i].getMax();
if (number <= max) {
return i;
}
}
return -1;
}
}
class block {
private int max; //最大值
private int startIndex; //起始索引
private int endIndex; //结束索引
public block() {
}
......
}
排序算法 Sort
冒泡排序 BubbleSort
相邻的元素两两比较，小的放前面，大的放后面
public static void bubbleSort(int[] arr) {
//外循环:要执行多少轮,n个数据要执行n-1轮
for (int i = 0; i < arr.length - 1; i++) {
//内循环:两两比较数据大小并交换位置
//-1:为了数组越界
//-i:提高效率,每一轮执行的次数要比上一轮少一次
for (int j = 0; j < arr.length - i - 1; j++) {
//如果后面的数小,就交换位置
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
选择排序 SelectionSort
从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较
小的放前面，大的放后面.第一轮循环结束后,最小的数据就已经到最左边了,
再继续循环,以此类推
public static void SSMethod(int[] arr) {
//外循环:i表示这一轮中,要拿哪个索引上的元素和后面其它元素比较并交换
//比较的次数(几轮):5个元素比较4次,所以要长度减一.
for (int i = 0; i < arr.length - 1; i++) {
//拿着i和它后面的数据进行比较交换,i后面的数据就是i+1
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;
}
}
}
}
插入排序 InsertSort
将数组分为有序和无序两组，遍历无序数据，将元素插入有序序列中即可。
//insertSort method
public static void insertSort1(int[] arr) {
//找到后面无序数列的第一个元素
int start = -1;
for (int i = 0; i < arr.length; i++) {
//后一个元素比前一个小就是有序数列的最后一个元素
if (arr[i] > arr[i + 1]) {
//加一就是无序数列的第一个元素
start = i + 1;
break;
}
}
//从start开始,遍历无序数列,得到每一个元素
for (int i = start; i < arr.length; i++) {
//记录当前要插入的数据索引,i往后遍历,j往前遍历
int j = i;
//注意:要(j > 0),如果j = 1 , arr[j-1]就是[0]索引.
while (j > 0 && arr[j] < arr[j - 1]) {
//交换位置
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
//继续和前面的元素进行比较
j--;
}
}
}
递归算法 Recursion
在方法中调用方法本身.
递归的两个核心:
-
找出口 : 什么时候不再调用方法.
-
找规则 : 把大问题变成小问题.
心得 : 方法内部再次调用方法时, 参数必须要更加靠近出口.
package algorithm;
public class recursion {
public static void main(String[] args) {
//求 1~100 的和
//100 + 99 + 98 + 97....+ 2 + 1 = ?
//大问题拆成小问题
//1~100之间的和 = 100 + (1~99之间的和)
//1~99之间的和 = 99 + (1~98之间的和)
//1~98之间的和 = 98 + (1~97之间的和)
//......
//1~2之间的和 = 2 + (1~1之间的和)
//1~1之间的和 = 1 (递归的出口)如果参数是一就不再调用方法了.
System.out.println(getSum(100));
}
public static int getSum(int number){
if (number ==1){
return 1;
}
return number + getSum(number - 1);
}
}
快速排序 QuickSort
-
将排序范围中的第一个数字作为基准数，再定义两个变量start, end
-
start从前往后找比基准数大的，end从后往前找比基准数小的。
-
找到之后交换start和end指向的元素，并循环这一过程，直到start和end 处于同一个位置，该位置是基准数在数组中应存入的位置，再让基准数归位。
-
基准数归位后的效果：基准数左边的，比基准数小，基准数右边的，比基准数大
-
最后用递归算法,排序基准数左边和右边的数据即可.
/*method
参数1:要排序的数组
参数2:要排序数组的起始索引
参数3:要排序数组的结束索引
*/
public static void quickSort(int[] arr, int i, int j) {
//定义两个变量记录要查找的范围
int start = i;
int end = j;
//定义递归的出口
if (start > end) {
return;
}
//记录基准数
int baseNumber = arr[i];
//利用循环找到要交换的元素,直到end和start指向同一个元素
while (start != end) {
while (true) {
//利用end,从后往前找,找比基准数大的元素
//或者start和end重合
if (end <= start || arr[end] < baseNumber) {
break;
}
end--;
}
while (true) {
//利用start,从前往后找,找比基准数小的元素
//或者start和end重合
if (end <= start || arr[start] > baseNumber) {
break;
}
start++;
}
//把start和end指向的元素交换
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//当start和end指向同一个元素时, 上面的循环就会结束
//表示已经找到了基准数再数组中应存入的位置
//就是拿着这个范围中的第一个数字,跟start指向元素交换
// <<基准数归位>>
int temp = arr[i];
arr[i] = arr[end];
arr[end] = temp;
//确定基准数左边的范围, 重复刚刚所作的事情, 递归调用
quickSort(arr, i, end - 1);
//确定基准数右边的范围, 重复刚刚所作的事情, 递归调用*/
quickSort(arr, end + 1, j);
}
Arrays类
Arrays
操作数组的工具类。
方法名 说明
public static String toString(数组） 把数组拼接成一个字符串
public static int binarySearch(数组，查找的元素） 二分查找法查找元素
public static int[] copyOf(原数组，新数组长度） 拷贝数组
public static int[] copyOfRange(原数组，起始索引，结束索引） 拷贝数组（指定范围）
public static void fill(数组，元素) 填充数组
public static void sort(数组） 按照默认方式进行数组排序
public static void sort(数组，排序规则) 按照指定的规则排序
toString 方法的底层和我们自己写的一样都是用StringBuilder拼接的字符串.
binarySearch方法查找的数组必须是有序的并且必须是升序的. 如果元素存在就返回索引, 如果要查找的元素不存在就返回插入点-1
copyOf方法, 参数1: 老数组 参数2 : 新数组的长度. 方法的底层根据第二个参数创建新的数组. 新数组长度小于老数组,会部分拷贝, 新数组长度等于老数组,会全部拷贝, 新数组长度大于老数组,会部分拷贝,剩余部分为默认初始化值.
copyOfRange拷贝数组(指定范围)方法,细节:包头不包尾,包左不包右.
sort排序方法 默认情况下,给基本数据类型升序排序, 底层为快速排序.
sort排序方法的重载: 参数1:要排序的数组 参数2:排序规则
只能给引用数据类型排序,如果数组是基本数据类型要变成所对应的包装类.
第二个参数为接口, 要传递这个接口的实现类对象, 作为排序的规则.采取匿名内部类.
compare的形式参数：
参数1: o1表示在无序序列中，遍历得到的每一个元素
参数2: o2有序序列中的元素
返回值：
负数: 表示当前要插入的元素是小的，放在前面
正数：表示当前要插入的元素是大的，放在后面
0 : 表示当前要插入的元素跟现在的元素比是一样的, 也会放在后面
结论 : 返回值是 o1 - o2 升序排列 o2 - o1 降序排列
Lambda表达式
函数式编程(Functional programming)的思想是忽略面向对象的复杂语法,强调做什么,而不是谁去做.
Lambda表达式就是函数式思想的体现.
Lambda表达式是JDK8后的新语法形式
注意点:
-
Lambda表达式可以用来简化匿名内部类的书写
-
Lambda表达式只能简化函数式接口的匿名内部类的写法
-
函数式接口：有且仅有一个抽象方法的接口叫做函数式接口，接口上方可以加@FunctionalInterface注解
1、Lambda表达式的基本作用？
简化函数式接口的匿名内部类的写法。
2、 Lambda表达式有什么使用前提？
必须是接口的匿名内部类，接口中只能有一个抽象方法
3、 Lambda的好处？
Lambda是一个匿名函数，我们可以把Lambda表达式理解为是一段 可以传递的代码，它可以写出更简洁、更灵活的代码，作为一种更紧 凑的代码风格，使Java语言表达能力得到了提升。
public static void main(String[] args) {
method(new swim() {
@Override
public void swimming() {
System.out.println("游泳~~");
}
});
method(
() -> {
System.out.println("Lambda游泳~~");
}
);
}
//利用匿名内部类的形式调用下面的方法
//调用方法时,如果方法参数是一个接口,那我们就要传递这个接口的实现类对象
//如果实现类对象只用一次,就可以用匿名内部类的形式书写
//method方法
public static void method(swim s) {
s.swimming();
}
//swim接口
@FunctionalInterface
interface swim {
void swimming();
}
Lambda表达式的省略写法
省略核心: 可推导, 可省略.
- 参数类型可以省略不写
- 如果只有一个参数,参数类型可以省略,同时()也可以省略
- 如果Lambda表达式的方法体只有一行,大括号,分号,return可以省略,这三个必须同时省略.
Integer[] arr = {1, 3, 5, 2, 4};
/*Lambda的省略规则
* 1.参数类型可以省略不写
* 2.如果只有一个参数,参数类型可以省略,同时()也可以省略
* 3.如果Lambda表达式的方法体只有一行,大括号,分号,return可以省略,这三个必须同时省略.
* */
//没有用Lambda表达式
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);
练习题 Lambda表达式简化Comparator接口的匿名形式
定义数组并存储一些字符串，利用Arrays中的sort方法进行排序
要求：
按照字符串的长度进行排序，短的在前面，长的在后面。
(暂时不比较字符串里面的内容)
String[] arr = {"aaa", "a", "aa", "aaaa"};
//匿名内部类写法
Arrays.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
});
//Lambda表达式的完整格式
Arrays.sort(arr, (String o1, String o2) -> {
return o1.length() - o2.length();
}
);
//Lambda表达式的省略写法
Arrays.sort(arr, (o1, o2) -> o1.length() - o2.length());
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
练习题
- 按照要求进行排序
定义数组并存储一些女朋友对象，利用Arrays中的sort方法进行排序
要求1:属性有姓名、年龄、身高。
要求2:按照年龄的大小进行排序，年龄一样，按照身高排序，
身高一样按照姓名的字母进行排序。 (姓名中不要有中文或特殊字符，会涉及到后面的知识）
/*1. 按照要求进行排序
定义数组并存储一些女朋友对象，利用Arrays中的sort方法进行排序
要求1:属性有姓名、年龄、身高。
要求2:按照年龄的大小进行排序，年龄一样，按照身高排序，
身高一样按照姓名的字母进行排序。 (姓名中不要有中文或特殊字符，会涉及到后面的知识）*/
public class SortGirls {
public static void main(String[] args) {
//创建对象
girl g1 = new girl("lucy", 13, 162);
girl g2 = new girl("peppa", 13, 161);
girl g3 = new girl("Ailee", 13, 161);
//创建数组
girl[] arr = {g1, g2, g3};
//排序 年龄->身高->名字
Arrays.sort(arr, new Comparator<girl>() {
@Override
public int compare(girl o1, girl 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));
}
}
//girlClass JavaBean
class girl {
private String name;
private int age;
private double height;
//......
}
//Lambda表达式
//排序 年龄->身高->名字
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;
});
- 不死神兔
有一对兔子，从出生后第三个月起每个月都生一对兔子 假如兔子都不死，问第十二个月的兔子对数为多少？
( 两种算法 : 1循环赋值 , 2 递归 )
public static void main(String[] args) {
/*2. 不死神兔
有一对兔子，从出生后第三个月起每个月都生一对兔子 假如兔子都不死，问第十二个月的兔子对数为多少？
( 两种算法 : 1循环赋值 , 2 递归 )*/
//斐波那契数列
//1 1 2 3 5 8 13 21 ... 前面两个数的和是第三个数.
// 1循环赋值
//创建一个长度为12的数组
int[] arr = new int[12];
//手动给0,1索引元素赋值
arr[0] = 1;
arr[1] = 1;
//利用循环给剩余的元素赋值
for (int i = 2; i < arr.length; i++) {
arr[i] = arr[i - 2] + arr[i - 1];
}
//获取最大索引上的数据
System.out.println(arr[11]);
//2 递归
//1递归的出口
//2递归的规律
//Fn(12) = Fn(11) + Fn(10);
//Fn(11) = Fn(10) + Fn(9);
//Fn(10) = Fn(9) + Fn(8);
//......
//Fn(3) = Fn(1) + Fn(2);
//Fn(2) = Fn(1);
//Fn(1) = Fn(1);
System.out.println(getSum(12));
}
public static int getSum(int mouth) {
if (mouth == 1 || mouth == 2) {
return 1;
} else return getSum(mouth - 1) + getSum(mouth - 2);
}
- 猴子吃桃
有一堆桃子，猴子第一天吃了其中的一半，并多吃了一个！以后每天猴子都吃当前剩下来的一半，然后再多吃一个，第10天的时候（还没吃），发现只剩下一个桃子了，请问，最初总共多少个桃子？
/*3. 猴子吃桃子
有一堆桃子，猴子第一天吃了其中的一半，并多吃了一个！以后每天猴子都吃当前剩下来的一半，
然后再多吃一个，第10天的时候（还没吃），发现只剩下一个桃子了，请问，最初总共多少个桃子？*/
public static void main(String[] args) {
/* p是桃子, 第10天 1
第9天 (1 + 1) * 2 = 4
第8天 (4 + 1) * 2 = 10
第7天 (10 + 1) * 2 = 22
......
* */
//利用循环解题
int peach = 1;
//吃了9天,循环9次
for (int i = 0; i < 9; i++) {
//每一天的桃子都是后一天数量加一再乘二
peach = (peach + 1) * 2;
}
System.out.println(peach); // 1534
System.out.println("------");
System.out.println(getPeach(1));// 1534
}
//利用递归解题
//
public static int getPeach(int day) {
if (day < 0 || day >= 11) {
System.out.println("时间错误");
return -1;
}
//递归的出口 第十天就剩一个了
if (day == 10) {
return 1;
//递归的规律: 每一天的桃子都是后一天数量加一再乘二,后一天就是day+1.
} else return (getPeach(day + 1) + 1) * 2;
}
- 爬楼梯
可爰的小明特别喜欢爬楼梯，他有的时候一次爬一个台阶，有的时候一次爬两个台阶。 如果这个楼梯有20个台阶，小明一共有多少种爬法昵？
运算结果：
1层台阶 1种爬法;
2层台阶 2种爬法;
7层台阶 21种爬法
/*可爰的小明特别喜欢爬楼梯，他有的时候一次爬一个台阶，有的时候一次爬两个台阶。
如果这个楼梯有20个台阶，小明一共有多少种爬法昵？
运算结果：
1层台阶 1种爬法;
2层台阶 2种爬法;
7层台阶 21种爬法*/
public static void main(String[] args) {
System.out.println(getCount(20));//10946
}
//参数为台阶数
public static int getCount(int n) {
//1层台阶 1种爬法;
if (n == 1) {
return 1;
}
//2层台阶 2种爬法;
if (n == 2) {
return 2;
}
//n层台阶, 就是n-1个台阶的爬法加上n-2个台阶的爬法
return getCount(n - 1) + getCount(n - 2);
}
//-------------------------------------
/*可爰的小明特别喜欢爬楼梯，他有的时候一次爬一个台阶，有的时候一次爬两个台阶,
有的时候一次爬三个台阶, 如果这个楼梯有20个台阶，小明一共有多少种爬法昵？
运算结果：
1层台阶 1种爬法;
2层台阶 2种爬法;
3层台阶 4种爬法;*/
public static void main(String[] args) {
System.out.println(getCount(20));//10946 -- 一次能跨3级台阶 13530
}
//参数为台阶数
public static int getCount(int n) {
//1层台阶 1种爬法;
if (n == 1) {
return 1;
}
//2层台阶 2种爬法;
if (n == 2) {
return 2;
}
//3层台阶 4种爬法;
if (n == 3){
return 4;
}
//n层台阶, 就是n-1个台阶的爬法加上n-2个台阶的爬法
return getCount(n - 1) + getCount(n - 2);
}