posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Stooge sort

Posted on 2007-07-25 14:13 ZelluX 阅读(672) 评论(0)  编辑  收藏 所属分类: Algorithm
CLRS page 161
伪代码描述:
Stooge-sort(A, i, j)
if A[i] > A[j]
    then exchange A[i], A[]
if i + 1  >= j
    then return
k = (j - i + 1) / 3
Stooge-sort(A, i, j - k)
Stooge-sort(A, i + k , j)
Stooge-sort(A, i, j - k)
即先排序前2/3部分,然后是后2/3部分,最后再进行前面1/3的排序。

a. 证明算法正确性
由于是递归算法,而初始状态显然成立,因此只要证明当部分排序正确时,整体也能够被正确排序:
第一次排序后,第二部分每个数都不小于第一部分的所有数;
第二次排序后,第二部分某些数被交换到第三部分中,此时第三部分数都不小于第二部分和第一部分的数,但是第二部分的数并不一定都小于第一部分的(因为可能包含第三部分的数,而这些数与第一部分数的大小关系无法确认);
第三次排序后,第二部分的数都不小于第一部分的数。
这样,第一部分的任意数<=第二部分的任意数<=第三部分的任意数
而且各部分的数都已排序,因此整体已被排序。

b. 复杂度分析
递归式
T(n) = 3T(2n/3) + 1
由Master Theorem

T(n) = O(n^log(3/2, 3))

只有注册用户登录后才能发表评论。


网站导航: