9-中位数和顺序统计量-算法导论

9-中位数和顺序统计量-算法导论

顺序统计量

定义

最小值与最大值-第一个顺序统计量为min，第n个~为最大值

获取最小值Minimum(A)

基本思想：将A[1]与后面n-1个数顺次比较得结果即可（共n-1次）

同时获取最大最小值

法1:像获取最小值那样，每次都将最小值与当前值比较，将最大值与当前值比较，计算次数为2n-2

中位数

上中位数&下中位数

功能: 返回A数组中第i小的元素

算法过程：

检查数组A是否为单一输入（if p==r 则直接返回A[p]）

功能: 确定n个不同元素的输入数组中第i小的元素

基本思路

通过 分组 获取中位数的中位数x，以此为分节点对输入进行划分，然后递归调用得出结果

算法过程

将含n个不同元素的输入数组A划分为[n/5]组

对每一组进行插入排序并得到该组中位数

若i==k则返回 x

最坏运行时间为O(n)。