快速排序

缘起

不客气的说, 快排已经是几乎每个库（c++ STL、java collection 甚至一些js库）中必备的API了, 由此可见其重要性.

快排是与堆排一样常用的内排序算法,但是更加简洁
快排属于交换排序（冒泡是另一种交换排序的初级版，但是冒泡稳定，快排不稳定(涉及不相邻元素的调换的排序都是不稳定的,例如希尔，堆排)），堆排属于选择排序（简单选择排序是另一种初级版，但是初级的选择排序与堆排都是不稳定的）
在时间复杂度上，快排可能最差到O（N^2）但是堆排一直很稳定O(N*logN)

Read More

无向连通图的最小生成树之Prim算法

缘起

【1】中我们引进了无向连通图的生成树的概念. 这里

将介绍最小生成树（MST minimal spanning tree）的概念. 即【1】中介绍的是无向连通图, 而本文准确的说, 介绍的是无向连通网——即在无向生成图的前提下，边是带权重的. 要求出所有生成树中边的权重之和最小的那棵生成树, 就是MST. MST在现实世界显然是有意义的, 例如整个城市要铺设网线, 打通各个城区, 但是两个城市之间铺设光缆的成本是不一样的. 这就是MST大显身手的舞台.

Read More

无向图的点双连通分量(又称块)

缘起

首先必须说清楚一些基本概念,1 割点（又叫关节点）、割边（又叫关节边或者桥）的意思就是弄掉它就不灵了（即原本的连通图就不连通了）

一个无向连通图存在割边（割点）的充要条件是边连通度=1（点连通度=1）而且割边割点的个数可以不止一个，

点连通度的意思是这个图最少删除掉多少个点可以使得图不再连通.边连通度的意思是这个图最少删掉多少条边可以使得图不再连通.

点（边）连通度>1的图叫做点（边）双连通图（或者叫重连通图），或者简称就是双连通图. 双连通分支（或者叫重连通分支）的概念就很明显了（双连通极大子图嘛），特别地，点双连通分支又叫做块.

本文就是要给出求块的算法. 其实就是在求割点的tarjan算法的过程中顺便干点事情.

Read More

无向连通图的割点

缘起

所谓无向连通图的关节点的意思是，删掉该节点之后, 无向连通图变得不连通了. 这就是关节点, 即割点. 较之其它顶点， 关节点更为重要。 在网络系统中它们对应于网关， 决定子网之间能否连通。 在航空系统中， 某些机场的损坏，将同时切断其它机场之间的交通。 故在资源总量有限的前提下， 找出关节点并重点予以保障， 是提高系统整体稳定性和鲁棒性的基本策略。

Read More