堆结构 堆与二叉树 堆结构是用数组实现的完全二叉树结构。 完全二叉树，通俗的解释就是，一颗二叉树要么每一层都是满的，要么不满的那一层也是正在从左向右填满的。 大根堆：完全二叉树中每棵子树的最大值都在顶部； 小根堆：完全二叉树中每棵子树的最小值都在顶部。 将数组表示为完全二叉树，其下标与二叉树节点有如下关系： 0 / \ 1 2 / \ / \ 3 4 5 6 节点左子节点：2 * i + 1 节点右子节点：2 * i + 2 父节点：(i - 1) / 2 有些实现会屏蔽掉数组的第 0 个下标，从下标 1 开始使用…

桶排序 桶排序的思想如下： 桶排序思想下的排序都是不基于比较的排序； 时间复杂度为 O(N)，额外空间复杂度为 O(M)； 应用范围有限，需要样本的数据状况满足桶的划分。 这里的桶可以由数组、队列、栈等等来实现，这是一种基于统计的排序算法。 常见的桶排序算法有计数排序和基数排序。 计数排序 计数排序的适用场景要求数据范围不大，且有规律。例如对员工按年龄排序。 通常可以假设员工的年龄是正整数，分布在 [0 ... 100]，我们就建立 100 个桶（Bucket）来统计这些数据。那么在一次 O(N)的遍历中，我们就可…

归并排序 传统的数组排序算法时间复杂度是 O(N^2)，因为每一次扫描数组，只能将 1 个数字移动到目标位置。每一个数的排序过程之间是互不关联的，也就浪费了一些有用的信息。 递归实现 我们用递归的思想来考虑排序问题，如果一个数组分为左右两部分，且两部分别都是有序的，那么我们只需要做一次 O(N)的操作，就可以将整个数组排序。这个操作就是归并排序核心的算法。 然后，为了合并整个大数组，我们先要将这个数组一分为二个部分，然后再继续分为两部分，直到达到最小子问题：当数组中只有一个元素时，他天然就是有序的。 public …