Java进阶学习笔记36——算法

什么是算法？

解决某个实际问题的过程和方法。

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