熟读而精思，循序而渐进，厚积而薄发。
简单实现了常见的几种内部排序算法，包括冒泡（Bubble），插入（Insert），快速排序（Quick Sort），堆排序（Heap Sort），归并（Merge），希尔排序（Shell Sort），并对这些算法的耗时在伪随机数上进行了简单的测试。
说明：
Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特•福特（Lester Ford）发明。Bellman-Ford算法的流程如下：
给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，
, Distant[s]为0；可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).
现有一个数列
，另有一个栈Stack和一个队列Queue，Stack与Queue初始为空。现对S中元素依次进行如下操作：
问最终队列Queue有多少种排列情况？聪明且见识广博的你或许一下子就可以说出答案：
现在对这个结果进行证明。
设1表示入栈操作，0表示出栈操作。那么上面对n个元素的入栈和出栈操作就构成了长度为2n的由0和1组成的序列，其中1和0的个数均为n个，在没有任何限制的情况下，一共有
个这样的序列。但是，这里的01序列是建立在一些列的入栈出栈操作的基础上的，因此就会受到入栈、出栈操作的限制。这里，唯一的限制就是栈为空时，无法进行出栈操作。反映到这个01序列中就是，任意位置之前，0的个数都能比1的个数多。因为有了01序列的总数，所以为了找出满足条件的序列的个数，只需要找出不符合条件的序列的个数。
Dijkstra算法是图论中的一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：集合T包含所有当前已经找到最短路径的点，初始情况下T中只有源点U = V – T，其中V为图G的点集。从源点开始，每次新扩展一个属于U、距离T中点最短的点，用该点更新U中的与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。若要处理含有负权值边的情况，就需要使用Bellman-Ford算法了。
在以下说明中，start为源，Adj[u,v]为点u和v之间的边的长度，结果保存在Closest[]
一个无向、加权、连通图的生成树是指这样一棵树，它包含该图所有的n个顶点，和该图边集E中的n-1个边。最小生成树就是该图所有生成树中各边权值之和（构造代价）最小的生成树。求指定图的最小生成树有多种算法，除了这里要介绍的Kruskal算法，还有Prim算法、Sollin算法等。
用Kruskal算法为无向加权连通图G构造最小生成树T的步骤如下：首先初始化T为一个包含所有n个顶点、0个边的森林，E为G的边集。每次从E中取出一条具有最小权值的边（并从E中删除该边），如果该边不与T中其他边构成回路，则将该边加入T，否则舍弃该边。重复上述操作至T中含有n-1条边，此时T即Kruskal算法构造出的最小生成树。
易证，对于一个无向加权连通图，总是存在一棵或以上的有限课生成树，而这些生成树中肯定存在至少一棵最小生成树。下面证明Kruskal算法构造的生成树是这些最小生成树中的一棵。
设T为Kruskal算法构造出的生成树，U是G的最小生成树。如果T==U那么证明结束。如果T != U，我们就需要证明T和U的构造代价相同。由于T != U，所以一定存在k > 0条边存在于T中，却不在U中。接下来，我们做k次变换，每次从T中取出一条不在U中的边放入U，然后删除U一条不在T中的边，最后使T和U的边集相同。每次变换中，把T中的一条边e加入U，同时删除U中的一条边f。e、f按如下规则选取：a). e是在T中却不在U中的边中最小的一条边；b). e加入U后，肯定构成唯一的一个环路，令f是这个环路中的一条边，但不在T中。f一定存在，因为T中没有环路。
设”此物”为x，则x满足同余方程组：
若存在x满足上述方程组，则
也满足该方程其中k任意整数，方程的最小正整数解满足
，即对3,5,7的最小公倍数求余。
在介绍求x的具体方法之前，先介绍两个简单的定理(证明从略)：
好久没写C++没用STL了，今天在STLChina泡了一下午。完整的代码只写了这么一个，贴上来吧。
写了两个类，Max_Heap和Min_Heap，以他们特例化priority_queue，可以方便地实现最大、最小堆。写完了忽然又觉得这俩类似乎是多此一举了，完全可以用greater
最后还写了测试用例：找出ｎ个数中最大的k个。
1 2 3 4 5 6 7 8 9 10 11 | /*
template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
explicit priority_queue ( const Compare& x = Compare(),
const Container& y = Container() );
template <class InputIterator>
priority_queue ( InputIterator first, InputIterator last,
const Compare& x = Compare(),
const Container& y = Container() );
*/ |
这里只给出一个简单的实现，具体原理参见Google、Baidu的各个角落及各大教材。做两点说明：
仅仅实现了必要的左旋、右旋处理，左平衡、右平衡操作，以及数据的插入操作，
不可重复插入数据。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | typedef int Type; //~ 节点数据类型 typedef struct Node { Type data; int bf; Node *left, *right; Node(){ bf = 0; left = right = 0; } } AVLNode, *AVLTree; //~ 平衡树及其节点 void RRotate(AVLTree & T) //~ 右旋处理,T的左孩子成为新子树根 { AVLNode * tmp = T->left; T->left = tmp->right; tmp->right = T; T = tmp; } |
这个排序算法为什么被命名为Shell排序，我一直幻想着它可能最早被用以Shell脚本吧，Just Now我才知道，发明人叫做Donald Shell，居然有人叫自己壳？
以前从来没有写过这个排序，事实证明，没写过基本等于没听说过、没学过。
21行的小程序花了我将近一个小时来调试，对一个大小为9的逆序用gdb跟踪了程序整个的执行过程，发现两处错误，迭代变量j的类型习惯性地写成了size_t，导致死循环，以后凡是这种i,j,k，一律int。还有就是把最外层的while(step > 0)写成了while(size > 0)，纯属自作自受。