算法讲解004【入门】选择、冒泡、插入排序

选择、冒泡、插入排序

• 前置知识：无

• 建议：会的同学直接跳过

• 本节内容：

• 选择排序一句话：i~n-1范围上，找到最小值并放在i位置，然后i+1~n-1范围上继续

• 冒泡排序一句话：0~i范围上，相邻位置较大的数滚下去，最大值最终来到i位置，然后0~i-1范围上继续

• 插入排序一句话：0~i范围上已经有序，新来的数从右到左滑到(和左边的数相比）不再小的位置插入，然后继续

算法讲解005【入门】对数器-验证的重要手段

对数器

• 建议：不要跳过，非常重要的自我验证技巧

对数器的试用场景

• 你在网上找到了某个公司的面试题，你想了好久，感觉自己会做，但是你找不到在线测试，你好心烦..

• 你和朋友交流面试题，你想了好久，感觉自己会做，但是你找不到在线测试，你好心烦..

• 你在网上做笔试，但是前几个测试用例都过了，突然一个巨大无比数据量来了，结果你的代码报错了，如此大的数据量根本看不出哪错了，甚至有的根本不提示哪个例子错了，怎么debug？你好心烦…

对数器的实现

1. 你想要测的方法a（最优解）

2. 实现复杂度不好但是容易实现的方法b（暴力解）

3. 实现一个随机样本产生器（长度也随机、值也随机）

4. 把方法a和方法b跑相同的输入样本，看看得到的结果是否一样

5. 如果有一个随机样本使得比对结果不一致，打印这个出错的样本进行人工干预，改对方法a和方法b

6. 当样本数量很多时比对测试依然正确，可以确定方法a（最优解）已经正确。

• 关键是第5步，找到一个数据量小的错误样本，便于你去带入debug

• 然后把错误例子带入代码一步一步排查

• Print大法、断点技术都可以

• 对数器的门槛其实是比较高的，因为往往需要在两种不同思路下实现功能相同的两个方法，暴力一个、想象中的最优解是另一个。

• 以后的很多题目都会用到对数器，几乎可以验证任何方法，尤其在验证贪心、观察规律方面很有用

• 到时候会丰富很多对数器的实战用法，这里只是一个简单易懂的示例

视频笔记

• 保持原数组不变，多拷贝两个用来测试的数组

• 如果有地方出错了，缩小数组长度和随机数大小

• 利用Print打印

算法讲解006【入门】二分搜索

二分搜索 大纲

• 二分搜索不一定发生在有序数组上
• 峰值元素是指其值严格大于左右相邻值的元素
• 给你一个整数数组 nums，已知任何两个相邻的值都不相等
• 找到峰值元素并返回其索引
• 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
• 你可以假设 nums[-1] = nums[n] = 无穷小
• 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
• 测试链接 : https://leetcode.cn/problems/find-peak-element/

视频笔记

• 要注意 left=m+1（如果在右侧） right=m-1 （如果在左侧） m=(left + right)/2 也可以 m = l +(r-l)/2 m = l + ((r-l)>>1) 防止溢出 && 位运算高效

• 2）可以使用二分，每次都查找，判断 m下标的数字 和 number 大小关系，然后根据情况更新left 和 right 和 m ，记得先定义一个 ans = -1 找到之后更新下标，直到 l==r

• 4）-1 和 n 位置都默认超小值
• 先看看第一个0位置和最后一个n-1是不是峰值，是返回，不是继续
• 中点 峰值 直接返回 否则 L为1 R为 n-2 往下走
• 左侧 > 中点，确定有中点，左侧二分
• 右侧 > 中点，确定有中点，右侧二分
• 左边上扬↗ 右边下降↘ 中间不管怎么连线，必有一个峰值

• 推广二分到某侧有 或 某侧没有

1. 在有序数组中确定num存在还是不存在

2. 在有序数组中找>=num的最左位置
1. package class006;​import java.util.Arrays;​// 有序数组中找>=num的最左位置public class Code02_FindLeft {​ // 为了验证 public static void main(String[] args) { int N = 100; int V = 1000; int testTime = 500000; System.out.println("测试开始"); for (int i = 0; i < testTime; i++) { int n = (int) (Math.random() * N); int[] arr = randomArray(n, V); Arrays.sort(arr); int num = (int) (Math.random() * V); if (right(arr, num) != findLeft(arr, num)) { System.out.println("出错了!"); } } System.out.println("测试结束"); }​ // 为了验证 public static int[] randomArray(int n, int v) { int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = (int) (Math.random() * v) + 1; } return arr; }​ // 为了验证 // 保证arr有序，才能用这个方法 public static int right(int[] arr, int num) { for (int i = 0; i < arr.length; i++) { if (arr[i] >= num) { return i; } } return -1; }​ // 保证arr有序，才能用这个方法 // 有序数组中找>=num的最左位置 public static int findLeft(int[] arr, int num) { int l = 0, r = arr.length - 1, m = 0; int ans = -1; while (l <= r) { // m = (l + r) / 2; // m = l + (r - l) / 2; m = l + ((r - l) >> 1); if (arr[m] >= num) { ans = m; r = m - 1; } else { l = m + 1; } } return ans; }​}​

3. 在有序数组中找<=num的最右位置

4. 二分搜索不一定发生在有序数组上（比如寻找峰值问题）