选择排序: 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。
但是这个算法的复杂度比较高,为$$n^2/2$$ 那为什么是这个值,假若我们放一张 n x n 的表格,然后我们在排序的过程中用灰色表示不变的元素,然后用黑色表示变化的元素。这样一来我们会发现这个表格是一个以对角线分隔的一个矩阵。很统一看到我们进行了二分之一的 n^2 扫描。
这个算法的另外一个问题就是无论我们的序列本来是否有序,我们...
在我们需要判断某一些事物之间是否存在一定的关系的时候,我们最好的办法不是使用图而是使用并查集。因为我们关心的是他们之间是否有关系,而不是关心的他们到底存在怎样的关系。
并查集,简单来说就是 n 个集合,我们通过 union 操作来建立两个节点之间的关系。通过 connected 来判断两个节点之间的关系。那么现在我们知道了 并查集的基本操作就是 union 和 connected 。
逻辑结构:并查集一开始我们初始化都是初始化 n 个不相关的独立集合。然后我们在做 un...