什么是算法?
解决某个实际问题的过程和方法。
1)导航;
2)滴滴打车;
3)抖音;
不同的算法,效率高、性能好!
在Java中,代码已经帮我们写好了,但为什么我们还要学习算法呢?
提升编程思维。
有些面试官就是问一些算法题。
算法是程序员的高级之路。
排序算法:
升序排序:由小到大;
降序排序:由大到小;
冒泡排序
选择排序
学习算法的技巧和路径:
1、搞清楚、理解算法的流程;
2、直接去推敲如何写代码;
冒泡排序:
每轮从数组中找出最大值放到数组的后面去。
两个两个地进行比较。
package cn.ensource.d1_algorithm;
import java.util.Arrays;
public class Test1 {
public static void main(String[] args) {
// 1. 准备一个数组
int[] arr = {5, 1, 2, 3};
// 定义一个循环,控制排几轮
for (int i = 0; i < arr.length - 1; i++) {
// i = 0 1 2
// 定义一个循环控制每轮比较几次
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;
}
}
}
// for (int i = 0; i < arr.length; i++) {
// System.out.println(arr[i]);
System.out.println(Arrays.toString(arr));
}
}
实现冒泡排序的关键步骤分析:
1)确定总共需要做几轮:数组的长度减一;
2)每轮比较的次数:
选择排序:
每轮选择当前位置,开始找出后面的较小值与该位置进行交换;
定位选择较小值。
package cn.ensource.d1_algorithm;
import java.util.Arrays;
public class Test2 {
public static void main(String[] args) {
// 1. 准备好一个数组
int[] arr = {5, 1, 3, 2};
// 2. 控制选择几轮
for (int i = 0; i < arr.length - 1; i++) {
// i = 0 1 2 j = 1 2 3 j = 2 3 j = 3
//
// 控制每轮选择几次
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;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
算法优化:
找到后面较小值的索引,然后只要交换一次。
package cn.ensource.d1_algorithm;
import java.util.Arrays;
public class Test2 {
public static void main(String[] args) {
// 1. 准备好一个数组
int[] arr = {5, 1, 3, 2};
// 2. 控制选择几轮
for (int i = 0; i < arr.length - 1; i++) {
// i = 0 1 2 j = 1 2 3 j = 2 3 j = 3
//
// 控制每轮选择几次
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// 决定是否交换
if (minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
}
基本查找:
顺序查找:
注意:在数据量很大的时候,基本查找这种从前往后挨个找的形式,性能差,效率地下。
二分查找、折半查找:
前提条件:数组中的数据必须是有序的。
核心思想:每次排除一半的数据,查询数据的性能明显提高很多。
package cn.ensource.d1_algorithm;
public class Test3 {
public static void main(String[] args) {
// 1. 准备好一个数组
int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
System.out.println("索引值为:" + binarySearch(arr, 81));
System.out.println("索引值为:" + binarySearch(arr, 150));
}
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
// 2. 定义一个循环控制折半
while (low <= high) { // 两个位置重合
// 3. 每次折半,都算出中间位置处的索引
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
// 往右边找,起始位置发生变化
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}
我们再看看API文档中是怎么写这个二分法查找算法的。
>>>是java中的移位运算符,表示无符号右移。
若对char,byte 或者short 进行移位处理,那么在移位进行之前,它们会自动转换成一个int。只有右侧的5 个低位才会用到。这样可防止我们在一个int 数里移动不切实际的位数。若对一个long 值进行处理,最后得到的结果也是long。此时只会用到右侧的6 个低位,防止移动超过long 值里现成的位数。
掌握编程思想;
面试。
我们再看我当时学Python的时候,学习二分法的方法:
https://changchunhua.blog.csdn.net/article/details/128228704