备战刷题《剑指offer》python的实现
1、把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置…. 我们对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会是最大的数。 除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。 性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 3、稳定排序 4、原地排序
首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法我们称之为选择排序。 性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 3、非稳定排序 4、原地排序
过程简单描述： 1、从数组第2个元素开始抽取元素。 2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。 3、继续选取第3，4，….n个元素,重复步骤 2 ，选择适当的位置插入。 性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 3、稳定排序 4、原地排序
希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。 希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。 希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。 性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 3、稳定排序 4、原地排序
将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。 通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。 性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(n) 3、稳定排序 4、非原地排序
我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。 从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。 性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(logn) 3、非稳定排序 4、原地排序
堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。 堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。 性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(1) 3、非稳定排序 4、原地排序
计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。 基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。 性质：1、时间复杂度：O(n+k) 2、空间复杂度：O(k) 3、稳定排序 4、非原地排序 注：K表示临时数组的大小，下同
桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。 之后每个桶里面的数据就是有序的了，我们在进行合并汇总。
- leetcode2 两数相加
- leetcode19 删除链表的倒数第N个节点
- leetcode21 合并两个有序链表
- leetcode23 合并K个排序链表
- leetcode24 两两交换链表中的节点
- leetcode25 k个一组翻转链表
- leetcode61 旋转链表
- leetcode82 删除排序链表中的重复元素II
- leetcode83 删除排序链表中的重复元素
- leetcode86 分隔链表
- leetcode206 反转链表
- leetcode92 反转链表II
- leetcode109 有序链表转换二叉搜索树
- leetcode138 复制带随机指针的链表
- leetcode141 环形链表
- leetcode142 环形链表II
- leetcode143 重排链表
- leetcode147 对链表进行插入排序
- leetcode148 排序链表
- leetcode160 相交链表
- leetcode203 移除链表元素
- leetcode206 反转链表
- leetcode234 回文链表
- leetcode237 删除链表中的节点
- leetcode318 奇偶链表
- leetcode445 两数相加II
- leetcode430 扁平化多级双向链表
- leetcode725 分隔链表
- leetcode876 链表的中间结点
- leetcode 1290 二进制链表转整数
- 剑指offer06_01 逆序打印链表
- 剑指offer06_02 逆序打印链表
- 剑指offer18_01 删除链表中的节点
- 剑指offer18_02 删除链表中的重复节点
- 剑指offer22_01 链表中倒数第k个节点
- 剑指offer22_02 求链表中的中间节点
- 剑指offer23 链表中环的入口节点
- 剑指offer24 反转链表
- 剑指offer25 合并两个排序的链表
- 剑指offer35_01 复杂链表的复制
- 真题 找出单向链表中的一个节点，该节点到尾指针的距离为K
- leetcode1 两数之和
- leetcode4 寻找两个有序数组的中位数
- leetcode11 盛最多水的容器
- leetcode15 三数之和
- leetcode16 最接近的三数之和
- leetcode26 删除排序数组中的重复项
- leetcode27 移除元素
- leetcode42 接雨水
- leetcode53 最大子序和
- leetcode62 不同路径
- leetcode63 不同路径II
- leetcode64 最小路径和
- leetcode75 颜色分类
- leetcode80 删除排序数组中的重复项II
- leetcode88 合并两个有序数组
- leetcode105 从前序与中序遍历序列构造二叉树
- leetcode126 单词接龙II
- leetcode209 长度最小的子数组
- leetcode219 存在重复元素II
- leetcode283 移动零
- leetcode695 岛屿的最大面积
- leetcode1013 将数组分成和相等的三个部分
- leetcode94 二叉树的中序遍历
- leetcode98 验证二叉搜索树
- leetcode102 二叉树的层次遍历
- leetcode103 二叉树的锯齿形遍历
- leetcode104 二叉树的最大深度
- leetcode105 从前序与中序遍历序列构造二叉树
- leetcode107 二叉树的层次遍历II
- leetcode144 二叉树的前序遍历
- leetcode145 二叉树的后序遍历
- leetcode199 二叉树的右视图
- leetcode235 二叉搜索树的最近公共祖先
- leetcode236 二叉树的最近公共祖先
- leetcode701 二叉搜索树中的插入操作
- leetcode5 最长回文子串
- leetcode53 最大子序和
- leetcode62 不同路径
- leetcode63 不同路径II
- leetcode64 最小路径和
- leetcode70 爬楼梯
- leetcode91 解码方式
- leetcode264 丑数II
- leetcode279 完全平方数
- leetcode98 验证二叉搜索树
- leetcode100 相同的树
- leetcode101 对称二叉树
- leetcode104 二叉树的最大深度
- leetcode105 从前序与中序遍历序列构造二叉树
- leetcode109 有序链表转换二叉搜索树
- leetcode110 平衡二叉树
- leetcode111 二叉树的最小深度
- leetcode112 路径总和
- leetcode113 路径总和II
- leetcode129 求根到叶子节点数字之和
- leetcode199 二叉树的右视图
- leetcode257 二叉树的所有路径
- leetcode695 岛屿的最大面积
- leetcode430 扁平化多级双向链表