堆排序描述

堆排序是利用堆这种数据结构所设计的一种排序算法。堆实际上是一个完全二叉树结构。

问：那么什么是完全二叉树呢？答：假设一个二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

我们知道堆是一个完全二叉树了，那么堆又分两种堆：大顶堆 和 小顶堆它们符合一个重要的性质：

• 小顶堆满足：Key[i] <= key[2i + 1] && Key[i] <= key[2i + 2] (父节点小于子节点)
• 大顶堆满足：Key[i] >= key[2i + 1] && Key[i] >= Key[2i + 2] (父节点大于子节点)

大顶堆最大的元素在跟节点，堆的性质决定了大顶堆中节点一定大于等于其子节点，反之，小顶堆的最小元素在根节点。我们来看看大顶堆和小顶堆的示意图:

堆排序基本思想及步骤

堆排序有以下几个核心的步骤：

1. 将待排序的数组初始化为大顶堆，该过程即建堆。
2. 将堆顶元素与最后一个元素进行交换，除去最后一个元素外可以组建为一个新的大顶堆。（获得当前最大的元素）
3. 将第二步堆顶元素跟最后一个元素交换后，新建立的堆不是大顶堆，需要重新建立大顶堆。重复上面的流程，直到堆中仅剩下一个元素。

more

贪心

与运算的用途

• 清零
• 取一个数的指定位：比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。
• 判断奇偶：只要根据最末位是0还是1来决定

基本框架

以dfs求深度为例：

1 2 3 4 5 6 7 8 9 10 11 12 13

class Solution: def maxDepth(self , root ): # write code here def depth(node): if node == None: return 0 a = depth(node.left) + 1 b = depth(node.right) + 1 return max(a,b) depth = depth(root) return depth

【自顶向下】从一个规模较大的问题 f(20)，向下逐渐分解规模，直到 f(1)、f(2)触底，再逐层返回答案，这就是【自顶向下】

【自顶向上】直接从最低下，最简单，问题规模最小的f(1)和f(2)开始往上推，直到推到想要的答案f(20)，这就是动态规划的思路。

---

求解动态规划的核⼼问题是穷举。

• 但是这类存在重叠子问题，直接暴力搜索效率较低。故需要一个备忘录或者DP Table，避免不必要的计算。

• 其一定具备最优子结构，才能通过子问题的最值得到原问题的最值。

• 由于问题千变万化，穷举所有可行解不不容易，故需要列出正确的状态转移方法。

重叠子问题，最优子结构，状态转移方程是动态规划的三要素。

写出状态转移方程一般是最难的，一个辅助框架：

明确 状态 -> 定义 dp数组/函数的含义 -> 明确 选择 -> 明确 base case。

摘自算法小抄

(52条消息) 排序算法时间复杂度、空间复杂度、稳定性比较_潘建南的博客-CSDN博客_排序算法的时间复杂度

• 时间复杂度记忆-

1. 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）
2. 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）

• 稳定性记忆-“快希选堆”（快牺牲稳定性）

1. 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

解决一个回溯问题，实际上就是一个决策树的遍历过程。需要考虑三个问题

1、路径：就是已经做出的选择

2、选择列表：就是当前可以做出的选择

3、结束的条件：就是到达决策树底层，无法在做选择的条件。

算法框架：

1 2 3 4 5 6 7 8 9

result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择/回溯

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

剑指 Offer 58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。