【单选】欲找到100个数字中的最大值和最小值所需要的最少比较

[不定项选择题]

【单选】欲找到100个数字中的最大值和最小值所需要的最少比较次数为

```
148
```
```
147
```
```
146
```
```
140
```

查看正确选项

你大锦哥

取刚好大小排序为50的一个数，让其他99个数与其比较有 49个数小于这个数 50个数大于这个数顺便比得最大值需要99次再比较49次得最小值共148次

发表于 2018-09-05 18:23:58 回复(0)

Love鱼小鱼

将100个数字随意分成50组进行比较，比较50次后得到两个大组，优胜组和失败组，每组50个数字，在优胜组中比较49次得到最大值，在失败组中比较49次得到最小值，一共需要比较：50 + 49 + 49 = 148（次）。

编辑于 2020-04-30 11:32:56 回复(0)

恋晨曦

我们知道，在一个容量为n的数据集合中寻找一个最大数，不管用什么样的比较算法，至少要比较n-1次，就算是用竞标赛排序也得比较n-1次，否则你找到的就不能保证是最大的数。那么，在一个容量为n的数据集合中同时寻找最大数和最小数的最小比较次数是多少呢？从一个容量为n的数据集合中同时找到最大数和最小数的最优方法是：首先让所有的元素参与两两比较，这样总共比较了n/2次，最大数肯定在胜者组中，最小数肯定在败者组中；然后从容量为n/2的胜者组中找到最大的数，最少要比较n/2 - 1次；同理，从容量为n/2的败者组中找到最小的数，最少要比较n/2 - 1次。所以总共需要比较(3n/2) - 2 次。以上假设n为偶数。奇数同理。

发表于 2018-09-05 21:36:14 回复(0)