算法导论第三版答案

SolutiontoExercise2.2-2

SELECTION-SORT.A/

nDA:length

forjD1ton 1

smallestDj

foriDjC1ton

ifA i <A smallest

smallestDi

exchangeA j withA smallest

Thealgorithmmaintainstheloopinvariantthatatthestartofeachiterationoftheouterforloop,thesubarrayA 1::j 1 consistsofthej 1smallestelementsinthearrayA 1::n ,andthissubarrayisinsortedorder.Afterthe rstn 1elements,thesubarrayA 1::n 1 containsthesmallestn 1elements,sorted,andthereforeelementA n mustbethelargestelement.

Therunningtimeofthealgorithmis .n2/forallcases.

算法导论第三版答案相关文档

最新文档

返回顶部