认识算法
什么是算法？
算法就像是一个厨房里的食谱。当你想做一道菜时，你需要按照食谱上的步骤来操作，确保每一步都做对了，这样才能做出美味的菜肴。同样地，算法就是一系列解决问题的步骤，它告诉计算机如何处理数据，从而得到我们想要的结果。
算法就像是一个聪明的助手，它可以帮助我们完成各种任务，比如排序、搜索、预测天气等等。只要我们给它正确的指令和数据，它就能按照预定的步骤，快速而准确地完成任务。
为什么要学习算法？
学习算法可以让我们更好地理解编程的本质，提高我们的编程能力。这样，我们就可以写出更好的程序，解决更复杂的问题。而且算法不仅可以用在计算机上，还可以用在生活中的很多地方。例如，烹饪食谱、旅行计划、投资策略等都可以看作是一种算法。
学习算法的技巧
- 理解问题：在尝试编写代码之前，首先要彻底理解问题。先搞清楚算法的流程。
- 逐步实现：将算法分解成小的、可管理的部分，并逐步实现它们。这可以使问题更容易处理，并允许你在每个步骤中进行测试和调试。
- 最后直接去推敲如何写代码。
那么下面就先来看两个简单的排序算法：
- 冒泡排序
- 选择排序
冒泡排序
介绍
从初始索引开始，当前索引与之后的索引两两比较，每比较完一次索引增加一次，每次从数组中找出最大值放在数组的后面去。
实现冒泡排序的关键步骤分析
- 确定总共需要做几轮：数组的长度 - 1
- 每轮比较几次：数组的长度 - i - 1 （i为当前的轮数 - 1）
- 当前位置大于后一个位置则交换数据
详细图解
假设我们要将一个数组按升序排序，从数组的第一个数和第二个数开始进行比较；
我们先来看第一轮排序：
| 第一轮比较的次数：3次 | （也就是数组的长度4 - 0（当前轮数 - 1） - 1） |
接下来看第二轮排序：
| 第二轮比较的次数：2次 | （也就是数组的长度4 - 1（当前轮数 - 1） - 1） |
那么第三轮比较的次数就为1次了。
该数组的长度为4，故而需要比较的轮数为：3次 （数组的长度 4 - 1）
由于冒泡排序的每一轮排序都会把一个最大或者最小的元素放在最后的位置，这个元素与前面所有的元素都比较过了，已经是确定的值，所以我们不再需要对它进行比较；所以每比较一轮，我们就少一个需要比较的元素。
代码部分
import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { //1.准备一个数组 int[] arr = {5,2,3,1}; //2.定义一个循环控制排几轮 for(int i = 0;i < arr.length - 1;i++){ //3.定义一个循环控制每轮比较几次 for(int j = 0; j < arr.length - i - 1;j++){ //判断当前位置的元素值，是否大于后一个位置的元素值，如果大则交换 if(arr[j] > arr[j + 1]){ arr[j + 1] = arr[j] ^ arr[j + 1]; arr[j] = arr[j] ^ arr[j + 1]; arr[j + 1] = arr[j] ^ arr[j + 1]; } } } System.out.println(Arrays.toString(arr)); } }
运行结果：
选择排序
介绍
- 每轮选择当前位置，开始找出后面的较小值（或较大值）与该位置交换。
比如第一轮比较：第一个元素分别与后面所有的元素进行比较，根据升序或降序进行交换。
选择排序的关键
- 确定总共需要选择几轮：数组的长度 - 1
- 控制每轮从以前位置为基准，与后面元素选择几次
还是以上一个数组为例子，
详细图解
第一轮比较了3次：
第二轮比较了2次：
第三轮就比较一次：
代码部分
import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { int[] arr = {5,1,3,2}; for(int i = 0; i < arr.length - 1; i++){ for(int j = i +1; j < arr.length; j++){ if(arr[i] > arr[j]){ arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } } } System.out.println(Arrays.toString(arr)); } }
运行结果：
选择排序优化
对于选择排序，其实我们可以稍加优化。不再进行多次的元素交换，而改为每轮排序都只交换一次，也就是说，我们可以在后面的索引中找到最小值（或最大值）与当前索引位置的元素进行一次比较，然后作一次交换即可。
图解
以图解的形式演示：
代码部分
import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { int[] arr = {5,1,3,2}; for(int i = 0; i < arr.length - 1; i++){ int minIndex = i; //记录最小值的索引 for(int j = i + 1; j < arr.length; j++){ if(arr[j] < arr[minIndex]){ minIndex = j; } } if(arr[i] > arr[minIndex]){ arr[i] = arr[i] ^ arr[minIndex]; arr[minIndex] = arr[i] ^ arr[minIndex]; arr[i] = arr[i] ^ arr[minIndex]; } } System.out.println(Arrays.toString(arr)); } }
运行结果：
同样的环境下，效率对比：
import java.util.Arrays; import java.util.Random; public class SelectionSort { public static void main(String[] args) { Random r = new Random(); int[] arr = new int[100000]; for (int i = 0; i < arr.length; i++) { arr[i] = r.nextInt(1000000) + 1; } long time1 = System.currentTimeMillis(); for(int i = 0; i < arr.length - 1; i++){ for(int j = i +1; j < arr.length; j++){ if(arr[i] > arr[j]){ arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } } } long time2 = System.currentTimeMillis(); // System.out.println(Arrays.toString(arr)); System.out.println("执行时间：" + (time2 - time1) / 1000.0 + "s"); } }
import java.util.Arrays; import java.util.Random; public class SelectionSort { public static void main(String[] args) { Random r = new Random(); int[] arr = new int[100000]; for (int i = 0; i < arr.length; i++) { arr[i] = r.nextInt(1000000) + 1; } long time1 = System.currentTimeMillis(); for(int i = 0; i < arr.length - 1; i++){ int minIndex = i; //记录最小值的索引 for(int j = i + 1; j < arr.length; j++){ if(arr[j] < arr[minIndex]){ minIndex = j; } } if(arr[i] > arr[minIndex]){ arr[i] = arr[i] ^ arr[minIndex]; arr[minIndex] = arr[i] ^ arr[minIndex]; arr[i] = arr[i] ^ arr[minIndex]; } } long time2 = System.currentTimeMillis(); // System.out.println(Arrays.toString(arr)); System.out.println("执行时间：" + (time2 - time1) / 1000.0 + "s"); } }
END
