[原创] zengyi820 2003-06-14
组合算法概论(A Brief Introduction to Combinatorial Algorithm)
组合算法是算法分析学当中非常重要的一个分支，关于它在计算机科学的地位我就不敖述了，下面为大家整理了整个材料，算法是我收集的，只是分门别类简单介绍一下，然后把我的材料做了个整理，大家收藏吧，感觉挺有用的，费了我好长时间和精力呀，我现在准备考研了，没有太多时间发很多经典文章了，这片算是大部头了。
关于组合学问题的算法，计算对象是离散的、有限的数学结构。从方法学的角度，组合算法包括算法设计和算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪心法等。下面我们着重谈谈几个有代表性的组合算法：
单纯形法：
这是一种线性规划算法，由G.B.Dantzig在1947年提出，后来由他和其他的学者又提出了单纯形法的变形和改进。这些被实践证明都是行之有效的，线性规划研究线性目标函数在一组线性等式与线性不等式约束下的极值问题。这本来是连续问题，Dantzig发现线性规划问题的可行解集（即满足约束条件的点的全体）是一个超多面体。如果它的最优解存在，那么这个最优解一定可以在超多面体的一个顶点取到。由于超多面体的顶点只有有限个，从而使线性规划成为一个组和优化问题。单纯形法是按照一定的规则，从可行解集的一个顶点转移到另一个顶点，使得目标函数的值不断地得到改进，最后达到最优。尽管单纯形法一直使用得很好，但是在最坏情况下它需要指数运行时间，从而使线性规划问题是否属于P类一度成为人们关心的问题。后来的椭球算法和投影算法都很好的解决了这个问题。
排序和检索：
这两部分应当是大家比较熟悉的，所谓排序，就是将给定的元素序列按照某种顺序关系重新排列成有序序列。例如将n个数组成的序列按照从小到大的顺序重新排列；将n个英语单词组成的的序列按照字典顺序重新排列。所谓检索，就是在给定的集合中查找某个特定的元素或是元素组。排序和检索已经成为计算机科学技术中最基本、使用最频繁的算法。下面我们专门谈谈排序算法（sorting algorithm）。
在讨论此种算法时，数据通常是指由若干记录组成的文件，每个记录包含一个或多个数据项，其中能够标志该记录的数据项称为键码。给定一文件的n个记录{R1,R2,…,Rn}及其相应的键码的集合{K1,K2,…,Kn}。所谓排序算法就是在数据处理中将文件中的记录按键码的一定次序要求排列起来的算法。若待排序的文件能够同时装入计算机的主存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，有一部分必须放在外存上，则称此类排序问题为外部排序。当待排序的文件中包含有一些相同键码的记录时，如果经过排序后这些相同的键码的记录的相对次序仍然保持不变，则相应的排序算法是稳定的，否则为不稳定的。如果排序算法设计成单处理机完成的，则此排序算法称为串行（或顺序）排序算法；如果排序算法时设计成多处理机实现的，则称为并行排序算法。
首先谈谈内部排序：内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。
使有序区中记录的数目增加一个或几个的操作称为一趟排序。
逐步扩大记录有序序列长度的方法大致有下列几类：
一．插入排序
假设在排序过程中，记录序列R[1..n]的状态为：
则一趟直接插入排序的基本思想为：将记录R
插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。
显然，完成这个“插入”需分三步进行：
1．查找R的插入位置j+1；
2．将R[j+1..i-1]中的记录后移一个位置；
3．将R复制到R[j+1]的位置上。
[I]直接插入排序
利用顺序查找实现“在R[1..i-1]中查找R的插入位置”的插入排序。
注意直接插入排序算法的三个要点：
1．从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；
R[0] = R; // 设置“哨兵”
for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找
return j+1; // 返回R的插入位置为j+1
2．对于在查找过程中找到的那些关键字不小于R.key的记录，可以在查找的同时实现向后移动；
for (j=i-1; R[0].key<R[j].key; --j);
R[j+1] = R[j]
3．i = 2，3，…, n, 实现整个序列的排序。
template<class Elem>
void InsertionSort ( Elem R[], int n)
{
// 对记录序列R[1..n]作直接插入排序。
for ( i=2; i<=n; ++i )
{
R[0] = R; // 复制为监视哨
for ( j=i-1; R[0].key < R[j].key; --j )
R[j+1] = R[j]; // 记录后移
R[j+1] = R[0]; // 插入到正确位置
}
} // InsertSort
时间分析：
实现排序的基本操作有两个：
（1）“比较”序列中两个关键字的大小；
（2）“移动”记录。
对于直接插入排序：
[II]折半插入排序
因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R的插入位置”，如此实现的插入排序为折半插入排序。其算法如下：
template<class Elem>
void BiInsertionSort (Elem R[]， int n)
{
// 对记录序列R[1..n]作折半插入排序。
for ( i=2; i<=L.length; ++i )
{
R[0] = R; // 将R暂存到R[0]
low = 1; high = i-1;
while (low<=high)
{ //在R[low..high]中折半查找插入的位置
m = (low+high)/2; // 折半
if (R[0].key < R[m].key))
high = m-1; // 插入点在低半区
else
low = m+1; // 插入点在高半区
}
for ( j=i-1; j>=high+1; --j )
R[j+1] = R[j]; // 记录后移
R[high+1] = R[0]; // 插入
}
} // BInsertSort
折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。
[III]表插入排序
为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。
算法描述如下：
template<class Elem>
void LInsertionSort (Elem SL[]， int n)
{
// 对记录序列SL[1..n]作表插入排序。
SL[0].key = MAXINT ;
SL[0].next = 1; SL[1].next = 0;
for ( i=2; i<=n; ++i )
for ( j=0, k = SL[0].next;
SL[k].key <= SL.key ; j = k, k = SL[k].next )
{ SL[j].next = i; SL.next = k; }
// 结点i插入在结点j和结点k之间
}// LinsertionSort
关于如在排序之后调整记录序列：
算法中使用了三个指针:
其中：p指示第i个记录的当前位置；
i指示第i个记录应在的位置；
q指示第i+1个记录的当前位置
template<class Elem>
void Arrange ( SLinkListType SL[ ], int n ) {
// 根据静态链表SL中各结点的指针值调整
// 记录位置，使得SL中记录按关键字非递减
// 有序顺序排列
p = SL[0].next;// p指示第一个记录的当前位置
for ( i=1; i<n; ++i ) {
// SL[1..i-1]中记录已按关键字有序排列，
// 第i个记录在SL中的当前位置应不小于i
while (p<i) p = SL[p].next;
// 找到第i个记录，并用p指示
// 其在SL中当前位置
q = SL[p].next; // q指示尚未调整的表尾
if ( p!= i ) {
SL[p]←→SL; // 交换记录，使第i个
// 记录到位
SL.next = p; // 指向被移走的记录，
// 使得以后可由while循环找回
}
p = q; // p指示尚未调整的表尾，
// 为找第i+1个记录作准备
}
} // Arrange
二． 交换排序
通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;
[I]起泡排序
假设在排序过程中，记录序列R[1..n]的状态为：n-i+1
则第i趟起泡插入排序的基本思想为：借助对无序序列中的记录进行“交换”的操作，将无序序列中关键字最大的记录“交换”到R[n-i+1]的位置上。
算法描述：
template <class Elem>
void BubbleSort(Elem R[], int n)
{
// i 指示无序序列中最后一个记录的位置
i = n;
while (i > 1) {
lastExchangeIndex = 1;
for (j = 1; j < i; j++) {
if (A[j+1] < A[j]) {
Swap(A[j],A[j+1]);
lastExchangeIndex = j;
} //if
} // for
i = lastExchangeIndex;
} // while
} // BubbleSort
起泡排序的结束条件为：最后一趟没有进行“交换”。
从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。我们可以设想，若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。
[II]一趟快速排序
目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t],且R[j].key≤ R.key ≤ R[j].key
(s≤j≤i-1) 枢轴 (i+1≤j≤t)
例如:关键字序列
52, 49, 80, 36, 14, 58, 61, 97, 23, 75
调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75
其中(52)为枢轴，在调整过程中，需设立两个指针:low和high，它们的初值分别为:s和t, 之后逐渐减小high，增加low，并保证R[high].key≥52，而R[low].key≤52,否则进行记录的“交换”。
算法描述如下:
template<class Elem>
int Partition (Elem R[], int low, int high) {
// 交换记录子序列R[low..high]中的记录，使
// 枢轴记录到位，并返回其所在位置，此时，
// 在它之前（后）的记录均不大（小）于它
pivotkey = R[low].key;
// 用子表的第一个记录作枢轴记录
while (low<high) {
// 从表的两端交替地向中间扫描
while (low<high && R[high].key>=pivotkey)
--high;
R[low]←→R[high];
// 将比枢轴记录小的记录交换到低端
while (low<high && R[low].key<=pivotkey)
++low;
R[low]←→R[high];
// 将比枢轴记录大的记录交换到高端
}
return low; // 返回枢轴所在位置
} // Partition
容易看出，调整过程中的枢轴位置并不重要，因此，为了减少记录的移动次数，应先将枢轴记录“移出”，待求得枢轴记录应在的位置之后(此时low=high),再将枢轴记录到位。
将上述“一次划分”的算法改写如下：
template<class Elem>
int Partition (Elem R[], int low, int high) {
// 交换记录子序列R[low..high]中的记录，使
//枢轴记录到位，并返回其所在位置，此时，
// 在它之前（后）的记录均不大（小）于它
R[0] = R[low];
// 用子表的第一个记录作枢轴记录
pivotkey = R[low].key; // 枢轴记录关键字
while (low < high) {
// 从表的两端交替地向中间扫描
while(low=pivotkey)
--high;
R[low] = R[high];
// 将比枢轴记录小的记录移到低端
while (low<high && R[low].key<=pivotkey)
++low;
R[high] = R[low];
// 将比枢轴记录大的记录移到高端
}
R[low] = R[0]; // 枢轴记录到位
return low; // 返回枢轴位置
} // Partition
[III]快速排序
在对无序序列中记录进行了一次分割之后，分别对分割所得两个子序列进行快速排序，依次类推，直至每个子序列中只含一个记录为止。 快速排序的算法描述如下:
template<class Elem>
void QSort (Elem R[], int low, int high) {
// 对记录序列R[low..high]进行快速排序
if (low < high-1) { // 长度大于1
pivotloc = Partition(L, low, high);
// 将L.r[low..high]一分为二
QSort(L, low, pivotloc-1);
// 对低子表递归排序，pivotloc是枢轴位置
QSort(L, pivotloc+1, high);
// 对高子表递归排序
}
} // QSort
template<class Elem>
void QuickSort(Elem R[], int n) {
// 对记录序列进行快速排序
QSort(R, 1, n);
} // QuickSort
快速排序的时间分析
假设一次划分所得枢轴位置i=k，则对n个记录进行快排所需时间
T(n) = Tpass(n)+T(k-1)+T(n-k)
其中 Tpass(n)为对n个记录进行一次划分所需时间，若待排序列中记录的关键字是随机分布的，则k取1至n中任意一值的可能性相同，由此可得快速排序所需时间的平均值为：
设 Tavg(1)≤b
则可得结果
通常，快速排序被认为是在所有同数量级O(nlogn)的排序方法中，其平均性能是最好的。但是，若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。
为避免出现这种情况，需在进行快排之前，进行“予处理”，即：比较 R(s).key, R(t).key和R[?(s+t)/2?.key，然后取关键字为“三者之中”的记录为枢轴记录。
三． 选择排序
从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;
[I]简单选择排序
假设排序过程中，待排记录序列的状态为：
并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟简单选择排序是，从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录加入有序序列。
简单选择排序的算法描述如下：
template
void SelectSort (Elem R[], int n ) {
// 对记录序列R[1..n]作简单选择排序。
for (i=1; i
// 选择第i小的记录，并交换到位
j = SelectMinKey(R, i);
// 在R[i..n]中选择key最小的记录
if (i!=j) R←→R[j];
// 与第i个记录交换
}
} // SelectSort
时间性能分析
对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为
移动记录的次数，最小值为0, 最大值为3(n-1)
[II]堆排序
