3.6次序统计.ppt

§(次序统计)---:已知n元数组A[1:n],确定其中第k最小的元。――最容易想到的算法是采用一种分类算法先将数组按不降的次序排好,然后从排好序的数组中捡出第k小的元素。但这样的算法在最坏情况下至少是O(nlogn),甚至可达O(n2)。实际上,我们可以设计出时间复杂性为O(n)的算法。§--分治策略划分侗瓮蔼奎***∈S,把S分成三个小集合s1,s2,s3例如,取m=63256669788s1s2s3如果k≤|s1|,那么k元就在s1中。如果k≤|s1|+|s2|,那么k元就在s2中,即k元就是m=6。如果k>|s1|+|s2|,那么k元就在s3中。这就把问题分成了小的问题,s1或s3。(n)算法,还必须:s1,s2都不超过S长的某固定分数,以便递归。显然,m最好是中间元或接近中间元。(n)。:例如,n=35,m=?,每个序列5个元,分别分拣好。把所有中间元合成序列M,求M序列中间元m。我们按上图:5个元小序列按纵向分拣(上小,下大),M是按横向分拣(左小,右大),那么由图可知:至少有的元大于或等于m,即小于m的元(集合s1)最多有个元。至少有的元小于或等于m,即大于m的元(集合s3)最多有个元。:查找S中第k最小元ProcedureFIND(k,S)()|S|<50thenbeginsortS;,不足5的余数另行处理;分拣5元小序列;设M为5元小序列中间元的集合;←FIND(,M),s2,s3;(m为分裂元,3个集合中的元分别小于、等于、大于m)|s1|≥kthenreturnFIND(k,s1)(|s1|+|s2|≥k)thenreturnmelse(即k元在s2中,也就是分裂元m)returnFIND(k-|s1|-|s2|,s3)end注:该算法语句编号与书上有区别!2和3是找中间元,3递归多次,直到|M|<50为止。,n=260第1轮:,(26,M);此时|M|=52(52个中间元的集合)第2轮:,余下的2个元暂置一边。(5,M1);此时|M1|=10第3轮:(m←M1的第5元)