算法集锦(四)AlanTu

在快速排序算法中，使用了分治策略。首先把序列分成两个子序列，递归地对子序列进行排序，直到整个序列排序结束。

步骤如下：

在序列中选择一个关键元素做为轴；

对序列进行重新排序，将比轴小的元素移到轴的前边，比轴大的元素移动到轴的后面。在进行划分之后，轴便在它最终的位置上；

递归地对两个子序列进行重新排序：含有较小元素的子序列和含有较大元素的子序列。

下面的动画展示了快速排序算法的工作原理。

快速排序图示：可以图中在每次的比较选取的key元素为序列最后的元素。

#include#includetypedefintElementType;#defineCutoff(3)

voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}voidWithSentrySort(ElementTypeA[],intN){inti,j;for(i=2;iA[0];j--){A[j+1]=A[j];}A[j+1]=A[0];}}

ElementTypeMedian3(ElementTypeA[],intLeft,intRight){intCenter=(Left+Right)/2;if(A[Left]>A[Center])swap(&A[Left],&A[Center]);if(A[Left]>A[Right])swap(&A[Left],&A[Right]);if(A[Center]>A[Right])swap(&A[Center],&A[Right]);

swap(&A[Center],&A[Right-1]);returnA[Right-1];}

voidQSort(ElementTypeA[],intLeft,intRight){inti,j;ElementTypePivot;if(Left+Cutoff<=Right){Pivot=Median3(A,Left,Right);i=Left;j=Right-1;for(;;){while(A[++i]Pivot);if(i

voidQuickSort(ElementTypeA[],intN){QSort(A,0,N-1);}

voidPrint(intA[],intn){inti;for(i=0;i

intmain(){constintMAX_ELEMENTS=10;intlist[MAX_ELEMENTS];inti=0;for(i=0;i

printf("排序之后：");Print(list,MAX_ELEMENTS);return0;}

运行结果：

0）引论

首先我们要明白什么叫做等价关系，而在这个之前要先有一个关系（relation）的定义

等价关系也是一种关系（Relation），只不过是要满足一些约束条件

a）aRa，对于所有属于S的a

b）aRb当且仅当bRa

c）aRb并且bRa意味着aRc

动态等价性问题：

定义在非空集合S上的关系R，对于任意属于数据集S中的每一对元素（a，b），确定aRb是否为真，也就是说a与b是否有关系。

而对于a与b是否有关系，我们只需要证明a与b是否在同一个等价类集合中。

1）基本结构

Find操作：返回给定元素的集合的名字，也就是检查a，b是否在同一个等价类中。对于Find运算，最重要的是判断Find（a，S）==Find（b，S）是否成立。

Union操作：如果a，b不在一个等价类中，可以用Union操作把这连个等价类合并为一个等价类。

我们可以用tree结构来表示一个集合，root可以表示集合的名字。由于仅有上面的两个操作而没有顺序信息，因此我们可以将所有的元素用1-N编号，编号可以用hashing方法。

a）使Find运行快

在数组中保存每个元素的等价类的名字，将所有等价类的元素放到一个链表中

b）使Union运行快

使用树来表示每一个集合，根节点表示集合的名字。数组元素P[i]表示元素i的父亲，若i为root，则P[i]=0。

对于Union操作，相当于把连个树合并，也就是指针的移动，如下图所示：

2）灵巧合并算法

上面的合并算法相当随意，它就是把第二棵树作为第一棵树的子树来完成合并操作。有一个简单的改进方法是总是让较小的树成为较大的树的子树，这种方法叫做Union-by-Size，如下图所示Union-by-Size可以降低树的深度，每个节点的深度都不会超过O(logN)。

为了实现这种方法，必须记录每一棵树的大小。我们可以另每一个根节点的数组元素表示树的大小的赋值，非根节点不变，依旧表示其父节点。这其实是把上面方法的数组中的0的位置做了一些利用。

另一种方法是Union-by-Height，也就是说我们把高度较浅的树作为高度较深的树的子树。亦即根节点记录的是树的高度的负值。

Union-by-Height的Union代码实现

路径压缩：在Find操作期间执行与Union操作无关，路径压缩的效果是从X到根节点的路径上的每一个结点都使它的父节点成为根节点。

代码实现：

路径压缩算法是与Union-by-Size相兼容的，与Union-by-Height并不完全兼容。

4）小应用

说了这么多，这个数据结构总要有点用处啊，否则就没有什么意义了。

一个例子是计算机网络和双向连接表，每一个连接将文件从一个计算机传递到另一个计算机。现在的问题是能否将文件从任意一个计算机传递到另一个任意的计算机，并且这个问题要on-line解决。

解决这个问题，就可以用到上面的数据结构。开始阶段我们可以把每一台计算机放到他自己的集合中，要求两台计算机传递文件当且仅当这两台计算机在同一个集合中。因此传输文件能力相当于一个等价关系。当我们需要传输文件时，检验两个计算机是否在同一个集合里，是的话就传输文件，否的话，就用Union方法把它们合并到一个集合中，然后传输文件。