🧮 Algorithm Notebook
1、算法准备
1.1 牛客网编程OJ的典型输入输出
2、算法框架
2.1 动态规划
2.1.1 斐波那契数列
2.1.2 背包问题
2.1.3 贪心算法
2.1.4 序列和数组类问题
2.1.5 编辑距离
2.1.6 高楼扔鸡蛋
2.1.7 股票问题系列通解
2.1.8 最长有效括号
2.1.9 剪绳子
2.1.10 正则表达式匹配
2.2 二分查找
2.2.1 二分查找框架
2.2.2 搜索旋转排序数组
2.3 链表
2.3.1 反转链表
2.3.2 相交链表
2.3.3 合并链表
2.3.4 链表中倒数第k个节点
2.3.5 复制带随机指针的链表
2.4 排序算法
2.4.1 常见排序算法
2.5 二叉树
2.5.1 二叉树遍历
2.5.2 岛屿问题
2.5.3 二叉树路径问题
2.5.4 构造二叉树
2.6 回溯算法
2.6.1 回溯算法解题框架
2.6.2 N皇后
2.7 数组
2.7.1 删除有序数组中的重复项
2.7.2 滑动窗口最大值
2.7.3 调整数组顺序使奇数位于偶数前面
2.7.4 螺旋矩阵
2.7.5 多数元素
2.7.6 最大数
2.7.7 和为s的两个数字
2.7.8 构建乘积数组
2.7.9 两数之和
2.8 字符串
2.8.1 最小覆盖子串
2.8.2 比较版本号
2.8.3 验证IP地址
2.8.4 基本计算器 II
2.8.5 字符串解码
2.8.6 移掉 K 位数字
2.8.7 无重复字符的最长子串
2.8.8 第一个只出现一次的字符
2.8.9 翻转字符串里的单词
2.8.10 字符串转换整数 (atoi)
2.8.11 字符串四则运算
2.9 栈
2.9.1 最小栈
2.9.2 弹出序列
2.10 数学
2.10.1 用 Rand7() 实现 Rand10()
2.10.2 只出现一次的数字
2.10.3 整数反转
2.10.4 求1+2+…+n
2.10.5 二进制中1的个数
2.10.6 幂运算
2.10.7 1~n 整数中 1 出现的次数
2.10.8 数字序列中某一位的数字
2.10.9 丑数
2.10.10 n个骰子的点数
2.10.11 圆圈中最后剩下的数字
2.10.12 不用加减乘除做加法
2.10.13 x 的平方根
2.11 设计
2.11.1 LRU 缓存机制
-
+
tourist
register
Sign in
常见排序算法
## 简单选择排序 ### 算法原理 1. 简单排序算法的基本思想为**每一趟从待排序的数据元素中选择最小(最大)的一个元素作为首元素,直到所有元素排完为止**。 ### 参考代码 1. 在算法实现时,每一趟确定最小元素的时候会通过**不断地比较交换**来使得**首位置为当前最小**。 2. **交换是个比较耗时的操作**,其实我们很容易发现,在还未完全确定当前最小元素之前,这些交换都是无意义的。 3. 我们可以通过设置一个变量 `minInd`,每一次比较仅存储较小元素的数组下标,当这一轮循环结束之后,那这个变量存储的就是当前最小元素的下标,此时再执行交换操作即可。 ```java /** * @author peng.wei * @version 1.0 * @date 2021/5/3 20:52 * @Description 简单选择排序算法 */ public class SimpleSelectionSort { public static void sort(int[] arr) { int m = arr.length; for (int i = 0; i < m - 1; i++) { int minInd = i; for (int j = minInd + 1; j < m; j++) { // 只记录最小元素的位置,而不是每一次比较都交换,减少交换的次数 if (arr[minInd] > arr[j]) {minInd = j;} } if (minInd != i) { // 如果当前位置 i 不是这一次的最小元素,再交换元素的位置 CommonUtils.swap(arr, i, minInd); } } } } ``` ### 算法分析 1. 简单排序算法无论数组原始排列如何,比较次数是不变的;对于交换操作,在最好情况下也就是数组完全有序的时候,无需任何交换移动,在最差情况下,也就是数组倒序的时候,交换次数为 `n-1` 次,综合下来,时间复杂度为 $O(n^2)$。 2. 简单排序算法是**不稳定**的排序算法。 ### 适用场景 1. 选择排序**实现也比较简单**,并且由于在各种情况下**复杂度波动较小**,因此一般是**优于冒泡排序**的。 2. 在所有的完全交换排序中,选择排序也是比较不错的一种算法,但是由于固有的 $O(n^2)$ 复杂度,选择排序在海量数据面前显得力不从心,因此,它**适用于简单数据排序**。 ## 冒泡排序 ### 算法原理 1. 冒泡排序的基本思想是**对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小(最大)的元素浮到顶端,最终达到完全有序**。 ![](https://notebook.ricear.com/media/202105/2021-05-04_183505.png) ### 参考代码 1. 在冒泡排序过程中,如果某一趟执行完毕,没有做任何一次交换操作,这就说明剩下的序列已经是有序的,排序操作也就可以完成了。 ```java /** * @author peng.wei * @version 1.0 * @date 2021/5/3 21:10 * @Description 冒泡排序算法 */ public class BubbleSort { public static void sort(int[] arr) { int m = arr.length; for (int i = 0; i < m - 1; i++) { // 判断是否需要交换 boolean exchange = false; for (int j = 0; j < m - i - 1; j++) { // 如果前面一个元素比后面一个元素大,则交换两个元素的位置,同时将 exchange 置为 true if (arr[j] > arr[j+1]) { CommonUtils.swap(arr, j, j+1); exchange = true; } } if (!exchange) { // 如果这一次冒泡没有发生交换,则说明前面的元素都已经有序了,没有必要再进行下一次冒泡了 break; } } } } ``` ### 算法分析 1. 对于冒泡排序算法,若原数组本身就是有序的,仅需 $n-1$ 次比较即可完成;若是倒序,比较次数为 $(n-1) + (n-2) + ... + 1 = n(n-1)/2$,交换次数和比较次数等值,所以,时间复杂度依然为 $O(n^2)$。 2. 综合来看,冒泡排序性能还是稍差于上面的**简单选择排序**的。 3. 在相邻元素相等时,他们不会交换位置,所以,冒泡排序是**稳定排序**。 ### 适用场景 1. 冒泡排序思路简单,代码也简单,特别**适合小数据的排序**,但是,由于**算法复杂度较高**,在**数据量大的时候不适用**。 ## 直接插入排序 ### 算法原理 1. 直接插入排序算法的基本思想是**每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止**。 ![](https://notebook.ricear.com/media/202105/2021-05-04_195701.png) ### 参考代码 ```java /** * @author peng.wei * @version 1.0 * @date 2021/5/3 21:28 * @Description 直接插入排序算法 */ public class DirectInsertionSort { public static void sort(int[] arr) { int m = arr.length; for (int i = 1; i < m; i++) { int j = i; while (j > 0 && arr[j - 1] > arr[j]) { CommonUtils.swap(arr, j - 1, j); j--; } } } } ``` ### 算法分析 1. 简单插入排序在**最好情况下**需要比较 $n-1$ 次,无需交换元素,**时间复杂度为 $O(n)$**;在最坏情况下,时间复杂度依然为 $O(n^2)$。 2. 但是,在**数组元素随机排列**的情况下,插入排序还是要**优于上面两种排序**的。 3. 由于只需要找到不大于当前数的位置而并不需要交换,因此,直接插入排序是**稳定排序**。 ### 适用场景 1. 简单插入排序由于 $O(n^2)$ 的复杂度,在数组较大时不适用,但是,当数据比较少的时候,是一个不错的选择,一般作为**快速排序的扩充**。 2. 例如,在 `JDK 7` 中的 `java.util.Arrays` 所用的 `sort` 方法的实现中,当待排序数组长度小于 47 时,会使用插入排序。 ## 希尔排序 ### 算法原理 1. 希尔排序也是一种**插入排序**,它是**简单插入排序**经过改进之后的一个更高效的版本,也称为**递减增量排序算法。** 2. 希尔排序的基本思想是**把记录按下标的一定增量分组,对每组使用直接插入算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止**。 3. **简单插入排序很循规蹈矩**,不管数组分布是怎样的,依然一步一步对元素进行比较、移动、插入,比如 $[5,4,3,2,1]$ 这种倒序序列,数组末端的 0 要回到首位是很费劲的,比较和移动元素均需 $n-1$ 次。 4. 而希尔排序在数组中采用**跳跃式分组**的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为 1。 5. 希尔排序通过这种策略使得整个数组**在初始阶段达到从宏观上看基本有序**,**小的基本在前**,大的基本在后,然后缩小增量,到增量为 1 时,大多数情况下只需微调即可,不会涉及过多的数据移动。 6. 希尔排序的具体排序过程如下: 1. 假如有这样一组数 $[13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]$,如果我们以步长为 5 开始进行排序,我们可以通过将这列表放在有 5 列的表中来更好的描述算法: ```txt 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ``` 2. 然后我们对每列进行**直接插入排序**: ```txt 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ``` 3. 然后再以 3 为步长进行排序: ```txt 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ``` 4. 排序之后的结果为: ```txt 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94 ``` 5. 最后再以 1 为步长进行排序,此时就是简单排序了。 ### 参考代码 ```java /** * @author peng.wei * @version 1.0 * @date 2021/5/4 19:34 * @Description 希尔排序 */ public class ShellSort { public static void sort(int[] arr) { int len = arr.length; // 增量 gap,并不断缩小增量 for (int gap = len / 2; gap >= 1; gap = gap / 2) { // 从第 gap 个元素开始,对每个组使用直接插入排序 for (int i = gap; i < len; i++) { int j = i; int temp = arr[i]; while (j - gap >= 0 && temp < arr[j - gap]) { // 将元素向后移动 gap 位 arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } } } ``` ### 算法分析 1. 希尔排序算法中对**增量序列的选择**十分重要,直接影响到希尔排序的性能,当选择增量序列为 $n/2^i$ 时,其最坏时间复杂度依然为 $O(n^2)$。 2. 希尔排序是**不稳定排序算法**。 ### 适用场景 1. 希尔排序虽然快,但是毕竟是插入排序,其数量级并**没有快速排序快**,在大量数据面前,希尔排序不是一个好的算法,但是**中小型规模的数据完全可以使用它**。 ## 快速排序 ### 算法原理 1. 快速排序是对**冒泡排序**的改进,冒泡排序每次只能交换相邻的两个元素,而快速排序是跳跃式的交换,交换的距离很大,因此总的比较和交换次数少了很多,速度也快了不少。 2. 快速排序的基本思想是: 1. 在待排序的元素**任取一个元素作为基准**(通常选第一个元素),称为**基准元素**。 2. 将待排序的元素进行**分区**,**比基准元素大的元素放在他的右边,比其小的放在他的左边**。 3. **对左右两个分区重复以上的步骤直到所有元素都是有序的**。 3. 快速排序算法的具体过程如下图: ![](https://notebook.ricear.com/media/202206/2022-06-27_110211_290113.gif) ### 参考代码 ```java /** * @author peng.wei * @version 1.0 * @date 2021/5/4 20:54 * @Description 快速排序算法 */ public class QuickSort { public static void sort(int[] arr) { quickSort(arr, 0, arr.length - 1); } /** * 快速排序算法 * @param arr 数组 * @param _left 左边界 * @param _right 右边界 */ public static void quickSort(int[] arr, int _left, int _right) { int left = _left; int right = _right; int temp = 0; if (left <= right) { // 待排序的第一个元素作为基准元素 temp = arr[left]; // 从左到有交替扫描,直到 left = right while (left != right) { // 从右往左扫描,找到第一个比基准元素小的元素 while (right > left && arr[right] >= temp) {right--;} // 找到这种元素 arr[right] 后与 arr[left] 交换 arr[left] = arr[right]; // 从左往右扫描,找到第一个比基准元素大的元素 while (left < right && arr[left] <= temp) {left++;} // 找到这种元素 arr[left] 后与 arr[right] 交换 arr[right] = arr[left]; } // 基准元素归位 arr[right] = temp; // 对基准元素左边的元素进行递归排序 quickSort(arr, _left, left - 1); // 对基准元素右边的元素进行递归排序 quickSort(arr, right + 1, _right); } } } ``` ### 算法分析 1. 当分区选取的基准元素为待排元素中的**最大或最小值**时,为**最坏的情况**,**时间复杂度**和直接插入排序的一样,移动次数达到最大值 $C_{max}=1+2+...+(n-1)=n*(n-1)/2=O(n^2)$。 2. 当分区选取的基准元素为待排序中的**中值**,为最好的情况,**时间复杂度为 $O(nlog_2n)$**。 3. 快速排序的**空间复杂度**为 $O(log_2n)$。 4. 当待排元素类似 $[6,1,3,7,3]$ 且基准元素为 6 时,经过分区,形成 $[1,3,3,6,7]$,两个 3 的相对位置发生了改变,所以快速排序是一种**不稳定排序算法**。 ### 适用场景 1. 快速排序在**大多数情况下**都是**适用**的,**尤其在数据量大的时候**性能优越更加明显,但在必要的时候,需要考虑下优化以提高其在最坏情况下的性能。 ### 扩展题目 #### 单链表快速排序 > 对于『将两个无序链表合并为一个新的有序链表』的题目,我们可以把两个无序链表连接为一个无序链表,然后对这个无序链表进行排序即可。 ##### 值交换 ###### 问题分析 1. 快速排序的思想就是**找一个 `pivot`**,**把小于 `pivot` 分在一边**,**大于等于 `pivot` 的分在另一边**。 2. 这个过程也叫做 `partition` 分区,数组的分区很好做,左右两个指针,不断交换就可以了,链表因为只能单向遍历,所以要换一种 `partition` 方法,目的是**使得左边的值都小于 `pivot`**,**右边的值都不小于 `pivot`**,所以**用一个索引记录左边的坐标**,**遍历过程中**,**每次碰到比 `pivot` 小的**,**都要交换一下**,**放到左边**,**遍历完成后**,**再把 `pivot` 放到中间来**,**这样就达成了目的**。 ![](https://notebook.ricear.com/media/202206/2022-06-27_170430_826067.gif) ###### 参考代码 ```java /** * @author peng.wei * @version 1.0 * @date 2021/9/20 15:08 * @Description 快速排序算法 */ public class QuickSort { /** * 使用单链表实现快速排序算法(值交换) * @param head 单链表头结点 * @return 排序后的单链表 */ public ListNode sortList(ListNode head) { quickSortWithValExchange(head, null); return head; } /** * 单链表快速排序算法(值交换) * @param head 单链表头结点 * @param tail 单链表尾节点 */ private void quickSortWithValExchange(ListNode head, ListNode tail) { if (head == tail || head.next == tail) {return;} int pivot = head.val; ListNode left = head, cur = head.next; while (cur != tail) { if (cur.val < pivot) { left = left.next; swap(left, cur); } cur = cur.next; } swap(head, left); quickSortWithValExchange(head, left); quickSortWithValExchange(left.next, tail); } /** * 交换链表中两个节点的值 * @param left 其中一个链表节点 * @param cur 另外一个链表节点 */ private void swap(ListNode left, ListNode cur) { int temp = left.val; left.val = cur.val; cur.val = temp; } } ``` ##### 指针交换 ###### 问题分析 1. 这道题目的解题方法如下: 1. 首先**对链表进行划分**。 2. 然后**递归调用**,**先重排右边的**,**然后把指针置空**,**再重排左边的**。 3. 最后**将左半部分和右半部分进行拼接即可**。 <iframe src="https://www.youtube.com/embed/jcNiKIYj6i8?list=PLHH5EZ_Bw-YGWD--DBu0-jqb2ptqG_Igg" width="100%" height="480" allow="autoplay" allowfullscreen="true"></iframe> ###### 5.5.1.2.2 参考代码 ```java /** * @author peng.wei * @version 1.0 * @date 2021/9/20 15:08 * @Description 快速排序算法 */ public class QuickSort { /** * 使用单链表实现快速排序算法(指针交换) * @param head 单链表头结点 * @return 排序后的单链表 */ public ListNode sortList(ListNode head) { return quickSortWithPointerExchange(head); } /** * 单链表快速排序算法(指针交换) * @param head 单链表头结点 * @return 排序后的单链表 */ private ListNode quickSortWithPointerExchange(ListNode head) { if (head == null || head.next == null) {return head;} int pivot = head.val; // 链表划分 ListNode ls = new ListNode(-1), rs = new ListNode(-1); ListNode l = ls, r = rs, cur = head; while (cur != null) { if (cur.val < pivot) {l.next = cur; l = l.next;} else {r.next = cur; r = r.next;} cur = cur.next; } l.next = rs.next; r.next = null; // 递归调用,先重排右边的,然后把指针置空,再重排左边的 ListNode right = quickSortWithPointerExchange(head.next); head.next = null; ListNode left = quickSortWithPointerExchange(ls.next); // 拼接左半部分和右半部分 cur = left; while (cur.next != null) {cur = cur.next;} cur.next = right; return left; } } ``` ## 堆排序 ### 算法原理 1. 堆是具有以下性质的完全二叉树: 1. **每个节点的值都大于或等于其左右孩子节点的值,称为大顶堆**。 2. **每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆**。 ![](https://notebook.ricear.com/media/202105/2021-05-05_203837.png) 2. 堆排序的基本思想为: 1. **将待排序序列构造成一个大顶堆**(构造大顶堆的时候选取的初始值为**最后一个非叶子节点**),此时,整个序列的**最大**值就是**堆顶的根节点**。 2. 将**堆顶的根节点与末尾元素进行交换**,此时**末尾元素就是最大值**。 3. 将剩余的 $n - 1$ 个元素看作一个新堆,**原来根的孩子节点仍是大顶堆**,而**新的根节点可能会违背最大堆的性质**,因此我们需要采用上面构造大顶堆的方法来**调整堆**,使其**符合大顶堆的性质**。 4. 然后重复上面交换新堆末尾元素和调整堆的过程,即可依次获取次小值,进而完成数据的排序。 <iframe src="https://www.youtube.com/embed/C6GtikVgWk8?list=PLHH5EZ_Bw-YGWD--DBu0-jqb2ptqG_Igg" width="100%" height="480" allow="autoplay" allowfullscreen="true"></iframe> ### 参考代码 ```java /** * @author peng.wei * @version 1.0 * @date 2021/5/5 19:49 * @Description 堆排序 */ public class HeapSort { public static void sort(int[] arr) { // 1. 构建大顶堆:从第一个非叶子节点开始从下至上,从右至左调整结构 int len = arr.length; // 第一个非叶子节点 int beginIndex = (len >> 1) - 1; for (int i = beginIndex; i >= 0; i--) { adjustHeap(arr, i, len - 1); } // 2.调整堆结构: // 2.1 每次都是移出最顶层的根节点,与最尾部节点位置调换,同时遍历长度-1。 // 2.2 然后重新整理被换到根节点的末尾元素,使其符合堆的特性。 // 2.3 直到未排序的堆长度为 0 for (int i = len - 1; i > 0; i--) { CommonUtils.swap(arr, 0, i); adjustHeap(arr, 0, i - 1); } } /** * 调整大顶推(仅是调整过程,建立在大顶堆已经构建的基础上) * @param arr 数组 * @param index 需要堆化处理的数据的索引 * @param length 未排序的数组的长度 */ public static void adjustHeap(int[] arr, int index, int length) { // 左子节点索引 int left = (index << 1) + 1; // 右子节点索引 int right = left + 1; // 子节点的最大索引,默认是左子节点 int max = left; // 如果左子节点索引超出范围,则直接返回 if (left > length) {return;} // 判断左右子节点哪个最大 if (right <= length && arr[right] > arr[left]) {max = right;} // 判断是否需要交换子节点和父节点: // 如果需要的话,则交换相应的子节点和父节点,然后调整换下父节点后的堆使其符合堆的特性 if (arr[max] > arr[index]) { CommonUtils.swap(arr, max, index); adjustHeap(arr, max, length); } } } ``` ### 算法分析 1. 堆排序算法**在最好和最坏情况下的时间复杂度都为 $O(nlog_2n)$**,**空间复杂度为 $O(1)$**。 2. 堆排序算法是**不稳定排序算法**。 ### 适用场景 1. 堆排序在**建立堆**和**调整堆**的过程中会产生比较大的开销,在**元素少的时候**并**不适用**,但是**在元素比较多的时候**还**是一个不错的选择**。 2. **在解决诸如 `前 n 的数` 一类问题时**,几乎**是首选算法**。 ### 扩展题目 #### 数组中的第 K 个最大元素] > 题目来源:[215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array)。 ##### 堆排序 ###### 问题分析 1. 我们可以构建一个大顶堆,然后在堆排序的过程中,每次调整大顶堆,我们都可以获取一个较大的元素,这样我们只需调整 $k$ 次,便可以将前 $k$ 大的元素排好位置,然后直接返回第 $arr.length - k$ 个元素即可。 2. 对于求**前 $k$ 大元素**的题目,一般用**堆排序**来解决。 ###### 参考代码 ```java /** * 调整堆 * @param arr 数组 * @param index 需要堆化处理的数据的索引 * @param length 未排序的数组的长度 */ public static void adjustHeap(int[] arr, int index, int length) { int left = (index << 1) + 1; int right = left + 1; int max = left; if (left > length) return; if (right <= length && arr[right] > arr[left]) {max = right;} if (arr[max] > arr[index]) { CommonUtils.swap(arr, max, index); adjustHeap(arr, max, length); } } /** * 堆排序 * @param arr 数组 * @param k 前几个数 */ public static void sort(int[] arr, int k) { // 1. 构造大顶堆 int length = arr.length; int beginIndex = (length >> 1) - 1; for (int i = beginIndex; i >= 0; i--) { adjustHeap(arr, i, length - 1); } // 2. 调整大顶堆 for (int i = length - 1; i >= length - k; i--) { CommonUtils.swap(arr, 0, i); adjustHeap(arr, 0, i - 1); } } /** * 215. 数组中的第 K 个最大元素(版本 2:堆排序) * @param nums 数组 * @param k 前几个数 * @return 第 K 个最大元素 */ public int findKthLargestV2(int[] nums, int k) { sort(nums, k); return nums[nums.length - k]; } ``` ##### 快速排序 ###### 问题分析 1. 该题目还可以利用 **快速排序** 来解决: 1. 快速排序每进行一次遍历,都会将一个元素放到其最终位置上,**左边的元素都小于该元素**,**右边的元素都大于该元素**。 2. 因此我们可以在完成一轮遍历后,判断 **当前已放置到最终位置的元素的位置 $cur$ 和目标元素的位置 $target$ 的关系**: 1. 如果 $target = cur$,说明当前元素就是目标元素,**直接返回** 即可。 2. 如果 $target < cur$,说明目标元素在当前元素的 **左边**,因此只 **向左边进行遍历** 即可。 3. 如果 $target > cur$,说明目标元素在当前元素的 **右边**,因此只 **向右边进行遍历** 即可。 > 目标元素的位置 $target$ 等于数组的长度减去 $k$。 ###### 参考代码 ```java /** * 采用快速排序查找目标位置的元素 * * @param arr 数组 * @param _left 左边界 * @param _right 右边界 * @param target 目标元素的位置 */ public static void quickSort(int[] arr, int _left, int _right, int target) { int left = _left, right = _right; int temp = 0; if (left <= right) { temp = arr[left]; while (left != right) { while (right > left && arr[right] >= temp) {right--;} arr[left] = arr[right]; while (left < right && arr[left] <= temp) {left++;} arr[right] = arr[left]; } arr[right] = temp; if (target == right) {return;} else if (target < right) {quickSort(arr, _left, left - 1, target);} else if (target > right) {quickSort(arr, right + 1, _right, target);} } } ``` #### 数据流中的中位数 > 题目来源:[剑指 Offer 41. 数据流中的中位数](https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof)。 ##### 问题分析 1. 我们可以**建立一个小顶堆 $A$ 和大顶堆 $B$**,**各保存列表的一半元素**,且规定: 1. **$A$ 保存较大的一半**,**长度为 $\frac{N}2$**($N$ 为偶数)**或 $\frac{N + 1}2$**($N$ 为奇数)。 2. **$B$ 保存较小的一半**,**长度为 $\frac{N}2$**($N$ 为偶数)**或 $\frac{N - 1}2$**($N$ 为奇数)。 2. 随后,**中位数可仅根据 $A、B$ 的堆顶元素计算得到**: ![Picture1.png](https://notebook.ricear.com/media/202202/2022-02-09_1419550.3791480604271996.png) 3. 算法流程如下: 1. **设元素总数为 $N = m + n$**,**其中 $m$ 和 $n$ 分别为 $A$ 和 $B$ 中的元素个数**。 2. `addNum(num)`**函数**: 1. **当 $m = n$**(即 $N$**为偶数**):**需向 $A$ 添加一个元素**,实现方法为**将新元素 $num$ 插入至 $B$**,**再将 $B$ 堆顶元素插入至 $A$**。 2. **当 $m \ne n$**(即 $N$**为奇数**):**需向 $B$ 添加一个元素**,实现方法为**将新元素 $num$ 插入至 $A$**,**再将 $A$ 堆顶元素插入至 $B$**。 > 假设插入数字 $num$ 遇到情况 1,由于 $num$**可能属于较小的一半**(即属于 $B$),因此**不能将 $num$ 直接插入 $A$**,**而应先将 $num$ 插入 $B$**,**再将 $B$ 堆顶元素插入至 $A$**,**这样就可以始终保持 $A$ 保存较大一半**,$B$**保存较小一半**。 3. `findMedian()`**函数**: 1. **当 $m = n$**(即 $N$**为偶数**):**则中位数为 $\frac{A 的堆顶元素 + B 的堆顶元素}2$**。 2. **当 $m \ne n$**(即 $N$**为奇数**):**则中位数为 $A$ 的堆顶元素**。 ##### 参考代码 ```java /** * 剑指 Offer 41. 数据流中的中位数 */ class MedianFinder { Queue<Integer> A, B; /** initialize your data structure here. */ public MedianFinder() { A = new PriorityQueue<>(); B = new PriorityQueue<>((x, y) -> (y - x)); } public void addNum(int num) { if (A.size() != B.size()) { A.add(num); B.add(A.poll()); } else { B.add(num); A.add(B.poll()); } } public double findMedian() { int size = A.size() + B.size(); if (size % 2 != 0) { return (double)A.peek(); } else { return (double)(A.peek() + B.peek()) / 2; } } } ``` ## 归并排序 ### 算法原理 1. 归并排序是**创建在归并操作上的一种有效的排序算法**。 2. 该算法是采用**分治法**(Divide and Conquer)的一种非常典型的应用,且各层递归可以同时进行。 3. 归并算法的具体过程如下(**分而治之**): ![](https://notebook.ricear.com/media/202105/2021-05-05_212356.png) 4. **合并相邻有序子序列**的方法: ![](https://notebook.ricear.com/media/202105/2021-05-05_212635.png) ![](https://notebook.ricear.com/media/202105/2021-05-05_212646.png) ### 参考代码 ```java /** * @author peng.wei * @version 1.0 * @date 2021/5/5 21:28 * @Description 归并排序 */ public class MergeSort { /** * 归并排序 * @param arr 数组 */ public static void sort(int[] arr) { int length = arr.length; int[] temp = new int[length]; sort(arr, 0, length - 1, temp); } /** * 归并排序(递归) * @param arr 数组 * @param left 左边界 * @param right 右边界 * @param temp 临时数组 */ public static void sort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = left + (right - left) / 2; // 左边归并排序,使得左子序列有序 sort(arr, left, mid, temp); // 右边归并排序,使得右子序列有序 sort(arr, mid + 1, right, temp); // 将两个有序子数组合并 merge(arr, left, mid, right, temp); } } /** * 合并两个序列 * @param arr 数组 * @param left 左边界 * @param mid 中间元素 * @param right 右边界 * @param temp 临时数组 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { // 左序列指针 int i = left; // 右序列指针 int j = mid + 1; // 临时数组指针 int t = 0; // 开始遍历左右两个序列 while (i <= mid && j <= right) { // 如果左边的元素小一些,则将左边的元素移动到 temp 数组中,同时左边的指针加 1 if (arr[i] <= arr[j]) {temp[t++] = arr[i++];} // 如果右边的元素小一些,则将右边的元素移动到 temp 数组中,同时右边的指针加 1 else if (arr[i] > arr[j]) {temp[t++] = arr[j++];} } // 将左边的剩余元素移动到 temp 中 while (i <= mid) {temp[t++] = arr[i++];} // 将右边的剩余元素移动到 temp 中 while (j <= right) {temp[t++] = arr[j++];} // 将 temp 中的元素全部拷贝到原数组中 t = 0; while (left <= right) {arr[left++] = temp[t++];} } } ``` ### ![](https://notebook.ricear.com/media/202105/2021-05-06_191525.png)算法分析 1. 归并排序算法**在最好情况下和最坏情况下的时间复杂度均为 $O(nlog_2n)$,空间复杂度为 $O(n)$。** 2. 归并排序算法是一种**稳定排序算法**,同时也是一种十分高效的排序算法,其速度仅次于快速排序。 ### 适用场景 1. 归并排序在**数据量比较大**的时候在**效率上**也**有较为出色的表现**。 2. 但是,其**空间复杂度**$O(n)$ 使得**在数据量特别大的时候**(例如 1000 万条数据)几乎**不可接受**,而且,考虑到有的机器内存本身就比较小,因此,**采用归并排序时一定要注意**。 ### 扩展题目 #### 数组中的逆序对 > 题目来源:[剑指 Offer 51. 数组中的逆序对](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof)。 ##### 问题分析 1. **[归并排序](#7-归并排序)与逆序对是息息相关的**,**归并排序体现了分而治之的思想**,**具体为**: 1. **分**:**不断将数组从中点位置划分开**,**将整个数组的排序问题转化为子数组的排序问题**。 2. **治**:**划分到子数组长度为 1 时**,**开始向上合并**,**不断将较短排序树组合并为较长排序树组**,**直至合并至原数组时完成排序**。 2. **合并阶段本质上是合并两个排序数组的过程**,**而每当遇到 $ 左子数组当前元素 \gt 右子数组当前元素 $ 时**,**意味着 $ 左子数组当前元素至末尾元素 $ 与 $ 右子数组当前元素 $ 构成了若干逆序对**。 3. **因此**,**考虑在归并排序的合并阶段统计逆序对数量**,**完成归并排序时**,**也随之完成所有逆序对的统计**。 ![Picture2.png](https://notebook.ricear.com/media/202202/2022-02-10_1954210.9101305560938778.png) ##### 参考代码 ```java /** * 剑指 Offer 51. 数组中的逆序对 * @param nums 数组 * @return 数组中的逆序对的总数 */ public int reversePairs(int[] nums) { int length = nums.length; int[] temp = new int[length]; return sort(nums, 0, length - 1, temp); } /** * 归并排序(递归) * @param arr 数组 * @param left 左边界 * @param right 右边界 * @param temp 临时数组 * @return 数组中的逆序对的总数 */ public int sort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = left + (right - left) / 2; // 左边归并排序,使得左子序列有序 int res = sort(arr, left, mid, temp); // 右边归并排序,使得右子序列有序 res += sort(arr, mid + 1, right, temp); // 将两个有序子数组合并 return merge(arr, left, mid, right, temp, res); } return 0; } /** * 合并两个序列 * @param arr 数组 * @param left 左边界 * @param mid 中间元素 * @param right 右边界 * @param temp 临时数组 * @return 数组中的逆序对的总数 */ public int merge(int[] arr, int left, int mid, int right, int[] temp, int res) { // 左序列指针 int i = left; // 右序列指针 int j = mid + 1; // 临时数组指针 int t = 0; // 开始遍历左右两个序列 while (i <= mid && j <= right) { // 如果左边的元素小一些,则将左边的元素移动到 temp 数组中,同时左边的指针加 1 if (arr[i] <= arr[j]) {temp[t++] = arr[i++];} // 如果右边的元素小一些,则将右边的元素移动到 temp 数组中,同时右边的指针加 1,然后统计逆序对的数量 else if (arr[i] > arr[j]) { temp[t++] = arr[j++]; res += mid - i + 1; } } // 将左边的剩余元素移动到 temp 中 while (i <= mid) {temp[t++] = arr[i++];} // 将右边的剩余元素移动到 temp 中 while (j <= right) {temp[t++] = arr[j++];} // 将 temp 中的元素全部拷贝到原数组中 t = 0; while (left <= right) {arr[left++] = temp[t++];} return res; } ``` ## 总结 ### 算法分类 十种常见排序算法可以分为两大类: * **比较类排序:** 通过**比较**来决定**元素间的相对次序**,由于其**时间复杂度不能突破 $O(nlogn)$**,因此也称为**非线性时间比较类排序**。 * **非比较类排序:不通过比较**来决定**元素间的相对次序**,他**可以突破基于比较排序的时间下界**,以线性时间运行,因此也称为**线性时间非比较类排序**。 ![](https://notebook.ricear.com/media/202105/2021-05-06_184235.png) ### 算法复杂度 * **稳定:** 如果 `a` 原本在 `b` 前面,且 `a=b`,排序之后 `a` 仍然在 `b` 前面。 * **不稳定:** 如果 `a` 原本在 `b` 前面,且 `a=b`,排序之后 `a` 可能会在 `b` 的后面。 * **时间复杂度:** 对排序数据的**总的操作次数**,反映当 `n` 变化时呈现什么规律。 * **空间复杂度:** 指**算法在计算机内执行时所需存储空间的度量**,他也是数据规模 `n` 的函数。 ![](https://notebook.ricear.com/media/202105/2021-05-06_191453.png) #### 稳定性 **稳定**的算法有:**插(如排序)、冒(泡排序)、归(并排序)、计(数排序)、桶(排序)、基(数排序)**。 **不稳定**的算法有:其他的 4 种都为不稳定的排序算法。 #### 时间复杂度 平均时间复杂度为 $O(nlog_2n)$ 的有:**堆(排序)、快(速排序)、归(并排序)**。 平均时间复杂度为 $O(n^{1.3})$ 的有:**希(尔排序)**。 平均时间复杂度为 $O(n^2)$ 的有:**插(入排序)、选(择排序)、冒(泡排序)**。 #### 空间复杂度 空间复杂度为 $O(1)$ 的有:**插(入排序)、希(尔排序)、选(择排序)、堆(排序)、冒(泡排序)**。 空间复杂度为 $O(n)$ 的有:**归(并排序)**。 空间复杂度为 $O(nlog_2n)$ 的有:**快(速排序)**。 ## 参考文献 1. [图解排序算法(一)之 3 种简单排序(选择,冒泡,直接插入)](https://www.cnblogs.com/chengxiao/p/6103002.html)。 2. [希尔排序](https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F)。 3. [图解快速排序](https://www.cnblogs.com/MOBIN/p/4681369.html)。 4. [快速排序算法详解(原理、实现和时间复杂度)](http://data.biancheng.net/view/117.html)。 5. [图解排序算法(三)之堆排序](https://www.cnblogs.com/chengxiao/p/6129630.html)。 6. [堆排序](https://zh.wikipedia.org/zh-cn/%E5%A0%86%E6%8E%92%E5%BA%8F)。 7. [图解排序算法(四)之归并排序](https://www.cnblogs.com/chengxiao/p/6194356.html)。 8. [【算法】排序算法之归并排序](https://zhuanlan.zhihu.com/p/124356219)。 9. [[算法总结] 十大排序算法](https://weiweiblog.cn/10sort)。 10. [十大经典排序算法(动图演示)](https://www.cnblogs.com/onepixel/p/7674659.html)。 11. [ 面试官:你写个链表快排吧(不准交换节点的值哦)](https://leetcode-cn.com/problems/sort-list/solution/gui-bing-pai-xu-he-kuai-su-pai-xu-by-a380922457)。 13. [面试题 41. 数据流中的中位数(优先队列 / 堆,清晰图解)](https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solution/mian-shi-ti-41-shu-ju-liu-zhong-de-zhong-wei-shu-y)。
ricear
Sept. 2, 2022, 8:52 p.m.
©
BY-NC-ND(4.0)
转发文档
Collection documents
Last
Next
手机扫码
Copy link
手机扫一扫转发分享
Copy link
Markdown文件
share
link
type
password
Update password