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

核心提示：程序1 4 - 7在最坏情况下的复杂性是( n2 )，此时left 总是为空，c语言算法 - 分而治之算法 - 选择排序(2)，而且第k个元素总是位于r i g h t.如果假定n是2的幂，则可以取消公式（2 - 1 0）中的向下取整操作符，当n≥1时有t(n)≤7 2cn(练习2 4 )，当元素互不相同时

程序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)可按如下递归公式来计算：

在上述递归公式中，假设当n＜9 0时使用复杂性为nl o gn的求解算法，当n≥9 0时，采用“中间的中间”规则进行分而治之求解。利用归纳法可以证明，当n≥1时有t(n)≤7 2cn(练习2 4 )。

当元素互不相同时，可以使用r=5来得到线性时间性能。