简单选择排序和堆排序
最近在全面学习数据结构，常用算法记录：简单选择排序和堆排序，简单选择排序的基本思想是每一趟在待排序元素中选取关键字最小的元素加入有序子序列，直到所有元素有序，总共进行 $n-1$ 趟。 堆排序的基本思想见文末图片。 简单选择排序为不稳定排序。 堆排序为不稳定排序。 简单选择排序时间复杂度： 时间复杂度：$O(n^2)$ 空间复杂度：$O(1)$ 堆排序时间复
数据结构
标签文章 8 篇
希尔排序
最近在全面学习数据结构，常用算法记录：希尔排序，基本思想是选定一个增量 $d<n$，将元素按此增量分组（所有相距 $d$ 的元素为一组），然后在各个子序列内进行插入排序，完成后缩小增量 $d'(d'<d)$，如此反复操作，直到增量 $d = 1$ 为止，此时就成了标准的插入排序，但此时大部分元素已经有序，只需要少量操作，甚至不用操作即可完成排序。该排序算法为
插入排序
最近在全面学习数据结构，常用算法记录：插入排序，基本思想是将待排序的记录按其关键字的大小逐个插入到一个有序序列（通常为左半部分），直到所有记录插入完成，是一种稳定排序。 空间复杂度：$O(1)$ 平均时间复杂度：$O(n^2)$
快速排序
最近在全面学习数据结构，常用算法记录：快速排序，即交换排序的一种，是对冒泡排序的一种改进，是一种不稳定排序。 平均时间复杂度：$O(nlogn)$ 最坏时间复杂度（退化至冒泡排序）：$O(n^2)$
堆排序
输入一个长度为 $n$ 的整数数列，从小到大输出前 $m$ 小的数。 输入格式 第一行包含整数 $n$ 和 $m$。 第二行包含 $n$ 个整数，表示整数数列。 输出格式 共一行，包含 $m$ 个整数，表示整数数列中前 $m$ 小的数。 数据范围 $\rm{1} \le m \le n \le {10^5}$ $\rm{1} \le 数列中的元素 \le {
滑动窗口（单调队列）
给定一个大小为 $n \le 10^6$ 的数组。 有一个大小为 $k$ 的滑动窗口，它从数组的最左边移动到最右边。 你只能在窗口中看到 $k$ 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子： 该数组为 $\left\{ {1,3, - 1, - 3,5,3,6,7} \right\}$，$k$ 为 $\rm{3}$。 窗口位置“[]”区域 最小
单调栈
给定一个长度为 $n$ 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 $-1$。 输入格式 第一行包含整数 $N$，表示数列长度。 第二行包含 $N$ 个整数，表示整数数列。 输出格式 共一行，包含 $N$ 个整数，其中第 $i$ 个数表示第 $i$ 个数的左边第一个比它小的数，如果不存在则输出 $-1$。 数据范围 $\rm{1} \le
数组模拟的双链表
实现一个双链表，双链表初始为空，支持 $\rm{5}$ 种操作： 在最左侧插入一个数； 在最右侧插入一个数； 将第 $k$ 个插入的数删除； 在第 $k$ 个插入的数左侧插入一个数； 在第 $k$ 个插入的数右侧插入一个数 现在要对该链进行 $M$ 次操作，进行完所有操作后，从左到右输出整个链表。 注意：题目中第 $k$ 个插入的数并不是指当前链表的第 $k