1.最大（小）值
（1）原理：
假设第一个值为最大值，逐一遍历后面的数，若比前面定义的最大值大，则用此值更新最大值。遍历完后即得序列中的最大值。获取最小值的算法同理可得。
（2）算法简要实现：最大值、最小值
（3）算法分析：
这里会有n－1次比较
耗时O（n），这显然是下界，因为至少要遍历一遍才知道所有数是什么
空间消耗为O（1），因为只定义了额外的记录max（min）的变量
2.最大值和最小值
（1）原理：
要同时找到序列中的最大值和最小值，可以仿照上面的算法同时定义两个变量（max、min）记录最大值和最小值，然后遍历后面的数，分别与最大值和最小值做比较，若大于最大值或小于最小值则分别更新最大值和最小值。这中算法显而易见，需要2（n－1）次比较。
我们这里可以采用另外一种算法减少需要的比较此数。首先根据元素的个数确定max和min的初始值，若元素的个数为奇数，则让初始max和min都为第一个值，若元素的个数为偶数，则让max为前两个数中的大值、min为前两个数中的小值；这样做是为了使得剩余元素的个数为偶数。然后我们每次向后遍历两个元素，先将这两个元素比较，然后将这两个元素中的大的和max进行比较，若大于则更新max，将两个元素中的小的和min进行比较，若小于则更新min。遍历到最后就可以得到整个序列的最大值和最小值了。
（2）算法简要实现：最大值和最小值
（3）算法分析：
一次完整的比较需要3次子比较，而总共有n／2次循环，所以只需要O（3/2n）次比较，减少了比较的次数
耗时O（n），系数比较小
空间消耗为O（1），只定义了max和min
3.序列中第k个值
输入：n个数的一个序列<a1，a2,...,an>，k
输出：ak，使得序列存在k－1个数不大于ak
要找到序列中的第k个值，我们可以首先对序列进行排序，然后把第k个值作为结果返回即可。这会在排序中耗去O（nlgn）的时间，下面提出更好的解决方案。
方案一
（1）原理：此方案和快排原理接近，回想快排算法，每此选定一个值，将比此值小的数放到它的左边，将比此值大的数放到它的右边。然后再分别对左子列和右子列重复进行上述过程，最终可以得到排好序数组。
注意到每做完一次partition过程实际上是确定了所选择的主元的位置（左边的比主元小、右边的比主元大）。而且要找序列第k个值，我们并不需要对两个子序列都进行“快排”，而只需要对目标所在序列进行“快排”即可。举例说明如下：加入我们有10个数，我们想找到其中的第5个数：如果第一次partition得到的恰为第5个位置，则此数即为结果；如果partition得到的大于第5个位置，说明第5个数在其左子列中，则继续对左子列进行“快排”；如果partition得到的小于第5个位置，说明第5个数在其右子列中，则继续对右子列进行“快排”，注意此时整个数列中的第五个数并不是右子列中的第5个数，要做相应的位置映射变换。
（2）算法简要实现：第k个值
（3）算法分析：
最坏为O（n*n）
期望为线性时间
方案二
（1）原理：
首先把序列5个一组划分，找出每一组的中位数
然后把这些中位数归为一组找到其中位数
然后以这个中位数作为主元进行“快排”
如果这个数的位置恰为k，则返回这个数，如果位置大于k，则在低区重复上述过程，否则在高区重复这一过程，在高区重复过程时注意进行位置映射变换
（2）算法简要实现：第k个值优化
（3）算法分析：
最坏为线性时间
网友评论