c语言算法 – 分而治之算法 – 选择排序

副标题#e#

对付给定的n个元素的数组a[0 : n – 1]，要求从中找出第k小的元素。当a[0 : n – 1]被排序时，该元素就是a[k – 1]。假设n=8，每个元素有两个域k e y和I D，个中k e y是一个整数，I D是一个字符。假设这8个元素为[( 1 2 ,a)，( 4 ,b)，( 5 ,c)，( 4 ,d)，( 5 ,e)，( 1 0 ,f)，( 2 ,g)，( 2 0 ,h)], 排序后获得数组[( 2 ,g)，( 4 ,d)，( 4 ,b)，( 5 ,c)，( 5 ,e)，( 1 0 ,f)，( 1 2 ,a)，( 2 0 ,h)]。假如k=1，返回I D为g 的元素；假如k=8，返回I D为h 的元素；假如k=6，返回是I D为f 的元素；假如k=2，返回I D为d 的元素。实际上，对最后一种环境，所获得的功效大概不独一，因为排序进程中既大概将I D为d 的元素排在a[1]，也大概将I D为b 的元素排在a[1]，原因是它们具有沟通巨细的k e y，因而两个元素中的任何一个都有大概被返回。可是无论如何，假如一个元素在k=2时被返回，另一个就必需在k=3时被返回。

选择问题的一个应用就是寻找中值元素，此时k=[n / 2]。中值是一个很有用的统计量，譬喻中间人为，中间年数，中间重量。其他k值也是有用的。譬喻，通过寻找第n / 4 , n / 2和3 n / 4这三个元素,可将人口分别为4份。

选择问题可在O( n l o g n )时间内办理，要领是首先对这n个元素举办排序（如利用堆排序式或合并排序），然后取出a[k – 1]中的元素。若利用快速排序（如图1 4 – 11所示），可以得到更好的平均机能，尽量该算法有一个较量差的渐近巨大性O( n2 )。

可以通过修写措施1 4 – 6来办理选择问题。假如在执行两个w h i l e轮回后支点元素a[l]被互换到a[j] ,那么a[l]是a[l : j]中的第j – l + 1个元素。假如要寻找的第k个元素在a[l : r]中，而且j – l + 1便是k，则谜底就是a[l]；假如j – l + 1 <k，那么寻找的元素是r i g h t中的第k – j + l – 1个元素，不然要寻找的元素是left中的第k个元素。因此，只需举办0次或1次递归挪用。新代码见措施1 4 – 7。S e l e c t中的递归挪用可用f o r或w h i l e轮回来替代（操练2 5）。

措施14-7 寻找第k个元素

template
T Select(T a[], int n, int k)
{// 返回a[0 : n - 1]中第k小的元素
// 假定a[n]是一个伪最大元素
if(k <1 || k >n) throw OutOfBounds();
return select(a, 0, n-1, k);
}
template
T select(T a[], int l, int r, int k)
{// 在a[l : r]中选择第k小的元素
if(l >=r) return a[l];
int i=l, // 从左至右的游标
j=r + 1; // 从右到左的游标
T pivot=a[l];
// 把左侧>=pivot的元素与右侧<=pivot 的元素举办互换
while(true) {
do {// 在左侧寻找>=pivot 的元素
i=i + 1;
} while(a[i] <pivot);
do {// 在右侧寻找<=pivot 的元素
j=j - 1;
} while(a[j] >pivot);
if(i >=j) break; // 未发明互换工具
Swap(a[i], a[j]);
}
if(j - l + 1==k) return pivot;
// 配置p i v o t
a[l]=a[j];
a[j]=pivot;
// 对一个段举办递归挪用
if(j - l + 1 <k)
return select(a, j+1, r, k-j+l-1);
else return select(a, l, j-1, k);
}

#p#副标题#e#

措施1 4 – 7在最坏环境下的巨大性是( n2 )，此时left 老是为空，并且第k个元素老是位于r i g h t.

假如假定n是2的幂，则可以打消公式（2 – 1 0）中的向下取整操纵符。通过利用迭代要领，可以获得t(n)=(n)。若仔细地选择支点元素，则最坏环境下的时间开销也可以酿成(n)。一种选择支点元素的要领是利用“中间的中间（ m e d i a n – o f – m e d i a n）”法则，该法则首先将数组a中的n个元素分成n/r 组，r 为某一整常数，除了最后一组外，每组都有r个元素。然后通过在每组中对r个元素举办排序来寻找每组中位于中间位置的元素。最后按照所获得的n/r其中间元素，递归利用选择算法，求得所需要的支点元素。

例2-6[中间的中间] 考查如下景象：r=5, n=27, 而且a=[2，6，8，1，4，1 0，2 0，6，2 2，11，9，8，4，3，7，8，1 6，11，1 0，8，2，1 4，1 5，1，1 2，5，4]。这2 7个元素可以被分为6组[2 , 6 , 8 , 1 , 4]，[1 0 , 2 0 , 6 , 2 2 , 11]，[9 , 8 , 4 , 3 , 7]，[8 , 1 6 , 11 , 1 0 , 8]，[2 , 1 4 , 1 5 , 1 , 1 2]和[5 , 4]，每组的中间元素别离为4 , 11 , 7 , 1 0 , 1 2和4。[4 , 11 , 7 , 1 0 , 1 2 , 4]的中间元素为7。这其中间元素7被取为支点元素。由此可以获得l e ft=[2 , 6 , 1 , 4 , 6 , 4 , 3 , 2 , 1 , 5 , 4]，m i d d l e=[7] ,r i g h t=[8 , 1 0 , 2 0 , 2 2 , 11 , 9 , 8 , 8 , 1 6 , 11 , 1 0 , 8 , 1 4 , 1 5 , 1 2]。

假如要寻找第k个元素且k<1 2，则仅仅需要在l e f t中寻找；假如k=1 2，则要找的元素就是支点元素；假如k>1 2，则需要查抄r i g h t中的1 5个元素。在最后一种环境下，需在r i g h t中寻找第(k- 1 2 )个元素。

定理2-2 当按“中间的中间”法则选取支点元素时，以下结论为真：

1) 若r=9, 那么当n≥9 0时，有m a x { |l e f e|, |r i g h t| }≤7n / 8。

2) 若r=5，且a中所有元素都差异，那么当n≥2 4时，有max{| left |, | right | }≤3n/ 4。

证明这个定理的证明留作操练2 3。

按照定理2 – 2和措施1 4 – 7可知，假如回收“中间的中间”法则并取r=9，则用于寻找第k个元素的时间t(n)可按如下递归公式来计较：

#p#分页标题#e#

在上述递归公式中，假设当n＜9 0时利用巨大性为nl o gn的求解算法，当n≥9 0时，回收“中间的中间”法则举办分而治之求解。操作归纳法可以证明，当n≥1时有t(n)≤7 2cn(操练2 4 )。

当元素互不沟通时，可以利用r=5来获得线性时间机能。