寻找数组的最大值与最小值

分手后的思念是犯贱 2022-05-15 06:13 333阅读 0赞

**问题：寻找数组中的最小值和最大值。**

一道很简单的题目，一般有下面4种解法：

1  遍历两次，每次分别找出最小值和最大值。

2  只遍历一次，每次取出的元素先与已找到的最小值比较，再与已找到的最大值比较。

3  每次取两个元素，将较小者与已找到的最小值比较，将较大者与已找到的最大值比较。

4  分治：将数组划分成两半，分别找出两边的最小值、最大值，则最小值、最大值分别是两边最小值的较小者、两边最大值的较大者。

这4种算法，哪种效率最高，哪种最低？

后两种算法只要进行1.5\*N次比较，因而网上有不少解答都将它们列为最佳答案。但是，算法4用到了递归，而递归法函数调用的开销是很大的，这就注定了该算法的效率肯定不高。那么，**算法3就是最高效的吗**？还是用代码来验证吧。

后面的代码，对每种算法都实现了两个函数（假设数组长度为N）：

算法1：solve\_1a与solve\_1b，后者加入两个临时变量，编译器可以将变量储存在寄存器中，不用每次循环都要写内存。比较次数为2\*N次。

算法2：solve\_2a与solve\_2b，前者每次循环必比较2次，后者最好情况下(递减数组)只要比较1次，但最差情况下（递增数组）则要比较2次，比较次数为：N到2 \* N次。

算法3：solve\_3a与solve\_3b，前者每次循环取头尾两元素（从两头往中间取），后者取相邻两元素。比较次数为1.5 \* N次。

算法4：solve\_4a与solve\_4b，后者返回一个结构（只有两个元素），编译器优化可以通过两个寄存器返回该结构，减少写内存次数。（检查gcc产生的汇编，确认有进行该优化）。比较次数为1.5 \* N次。

下面是测试结果：（数组长度为6e7，每种算法测4次取平均值）

<table> 
 <tbody> 
 <tr> 
 <td> &nbsp; </td> 
 <td colspan="5"> 所用时间（毫秒，GCC 4.5） </td> 
 <td colspan="5"> 所用时间（毫秒，VC 2010） </td> 
 </tr> 
 <tr> 
 <td> 函数名 </td> 
 <td> 递增 </td> 
 <td> 递减 </td> 
 <td> 乱序1 </td> 
 <td> 乱序2 </td> 
 <td> 乱序3 </td> 
 <td> 递增 </td> 
 <td> 递减 </td> 
 <td> 乱序1 </td> 
 <td> 乱序2 </td> 
 <td> 乱序3 </td> 
 </tr> 
 <tr> 
 <td> 1a 两次遍历 </td> 
 <td> 175 </td> 
 <td> 183 </td> 
 <td> 187 </td> 
 <td> 179 </td> 
 <td> 179 </td> 
 <td> 199 </td> 
 <td> 203 </td> 
 <td> 176 </td> 
 <td> 187 </td> 
 <td> 175 </td> 
 </tr> 
 <tr> 
 <td> 1b 两次遍历（优化） </td> 
 <td> 175 </td> 
 <td> 179 </td> 
 <td> 171 </td> 
 <td> 171 </td> 
 <td> 172 </td> 
 <td> 183 </td> 
 <td> 234 </td> 
 <td> 175 </td> 
 <td> 187 </td> 
 <td> 172 </td> 
 </tr> 
 <tr> 
 <td> 2a 一次遍历 </td> 
 <td> 105 </td> 
 <td> 105 </td> 
 <td> 105 </td> 
 <td> 129 </td> 
 <td> 105 </td> 
 <td> 105 </td> 
 <td> 132 </td> 
 <td> 105 </td> 
 <td> 109 </td> 
 <td> 105 </td> 
 </tr> 
 <tr> 
 <td> 2b 一次遍历（优化） </td> 
 <td> 105 </td> 
 <td> 90 </td> 
 <td> 105 </td> 
 <td> 109 </td> 
 <td> 105 </td> 
 <td> 109 </td> 
 <td> 109 </td> 
 <td> 105 </td> 
 <td> 113 </td> 
 <td> 105 </td> 
 </tr> 
 <tr> 
 <td> 3a 取头尾两元素 </td> 
 <td> 85 </td> 
 <td> 85 </td> 
 <td> 246 </td> 
 <td> 246 </td> 
 <td> 246 </td> 
 <td> 86 </td> 
 <td> 82 </td> 
 <td> 261 </td> 
 <td> 261 </td> 
 <td> 261 </td> 
 </tr> 
 <tr> 
 <td> 3b 取相邻两元素 </td> 
 <td> 93 </td> 
 <td> 101 </td> 
 <td> 238 </td> 
 <td> 242 </td> 
 <td> 238 </td> 
 <td> 93 </td> 
 <td> 101 </td> 
 <td> 258 </td> 
 <td> 257 </td> 
 <td> 253 </td> 
 </tr> 
 <tr> 
 <td> 4a 分治法 </td> 
 <td> 316 </td> 
 <td> 359 </td> 
 <td> 867 </td> 
 <td> 863 </td> 
 <td> 867 </td> 
 <td> 773 </td> 
 <td> 777 </td> 
 <td> 1554 </td> 
 <td> 1558 </td> 
 <td> 1558 </td> 
 </tr> 
 <tr> 
 <td> 4b 分治法（优化） </td> 
 <td> 273 </td> 
 <td> 289 </td> 
 <td> 824 </td> 
 <td> 824 </td> 
 <td> 828 </td> 
 <td> 648 </td> 
 <td> 656 </td> 
 <td> 1347 </td> 
 <td> 1340 </td> 
 <td> 1339 </td> 
 </tr> 
 </tbody> 
</table>

编译参数：tdm-gcc 4.5.2-dw2:  g++ -O3 -s -Wextra –Wall     VC 2010:  cl /Ox /EHsc /nologo /W3

很明显，“**分治”法的效率远低于其它3种算法**。对前3种算法，将数组长度增加到1e8，并对十组随机数组进行测试，得到结果：

![0_1304436412234Q.gif][]

从上面的表和图可以看出，算法3在数组有序时，运行效率很高（但与算法2相差不大），而在乱序时，甚至比两次遍历都慢。乱序时：**算法2效率最高，算法1次之，算法3效率最低。**

算法2a和算法2b的效率差不多，有时算法2a的效率还略高。算法2a，每次循环都要比较2次，算法2b每次循环要比较1到2次，但由于前者的两次比较是无关的，后者的比较是相关的（第一次比较的结果决定是否进行第二次比较），在现代CPU“指令预测”等技术前，算法2a在某些情况下能比较算法2b更高效。

算法3的效率也不是绝对最差的，上面的随机数组是通过随机产生一些数得到，如果把它改为对数组的元素进行 “随机洗牌”，就得到下面的结果（所得的新数据与上面的数据和并，下图中第一、三列是上面的数据，第二、四列是改用“随机洗牌”后得到的新数据）：

![0_13044364475NMv.gif][]

从图可以看出，改用“随机洗牌”法得到乱序数组后，VC的结果没发生改变，GCC除了函数3a，结果也没改变，但是“3a一次取头尾两元素”却成为最高效的算法，但其效率和 “一次遍历取一个元素” 法，相差并不是太大。因而可以说，在单线程环境下，**“一次遍历取一个元素”**这个最容易想到的方法，反而**是本题的最佳解法**。

算法上的最优，并不一定是实际上的最优，快排和堆排序就是一个典型的例子，虽然快排最坏情况下的复杂度是O(N^2)，而堆排序始终是O(N lgN)，但实际运用中，一个好的快排实现一般都比堆排序快很多。何况这4种算法的复杂度还都是O(N)。为了在最坏情况下节省0.5 \* N次比较，进行的所谓优化，得到的结果很可能与所期望的恰恰相反。

01.// by flyinghearts # qq.com 
 02. 
 03.#include <algorithm> 
 04.#include <limits> 
 05.#include <vector> 
 06.#include <cstdio> 
 07. 
 08.#define NOMINMAX 1 
 09.#include <windows.h> 
 10. 
 11.#define TEST_CASE 1 // 第0组还是第1组测试 
 12.#define RANDOM_SHUFFLE 0 // 乱序是否通过随机洗牌获得 
 13. 
 14. 
 15.#define TEST_RAND_POS 0 
 16.const unsigned Pack = 4; // 对某组数据连续测试Pack次，取平均值 
 17.const unsigned Rand_M = 5; // 测试某个乱序数组的 Rand_M个子数组 
 18.#if ! TEST_CASE 
 19. const unsigned Fix_M = 3; // 固定数组长度时，测试Fix_M个乱序数组 
 20. const unsigned Length = 6e7; // 固定数组长度 
 21.#else 
 22. const unsigned Fix_M = 10; 
 23. const unsigned Length = 1e8; 
 24.#endif 
 25. 
 26.#if _MSC_VER 
 27. #pragma comment(lib, "winmm.lib") 
 28.#endif 
 29. 
 30.inline unsigned mclock() { return timeGetTime(); } 
 31. 
 32.void solve_1a(const int arr[], const size_t len, int& min_value, int& max_value) 
 33.{ 
 34. min_value = max_value = arr[0]; 
 35. for (const int *p = arr + 1; p < arr + len; ++p) 
 36. if (*p < min_value) min_value = *p; 
 37. for (const int *p = arr + 1; p < arr + len; ++p) 
 38. if (*p > max_value) max_value = *p; 
 39.} 
 40. 
 41. 
 42.void solve_1b(const int arr[], const size_t len, int& min_value, int& max_value) 
 43.{ 
 44. int max_v = arr[0], min_v = arr[0]; 
 45. for (const int *p = arr + 1; p < arr + len; ++p) 
 46. if (*p < min_v) min_v = *p; 
 47. for (const int *p = arr + 1; p < arr + len; ++p) 
 48. if (*p > max_v) max_v = *p; 
 49. max_value = max_v; 
 50. min_value = min_v; 
 51.} 
 52. 
 53. 
 54.void solve_2a(const int arr[], const size_t len, int& min_value, int& max_value) 
 55.{ 
 56. int max_v = arr[0], min_v = arr[0]; 
 57. for (const int *p = arr + 1; p < arr + len; ++p) { 
 58. if (*p < min_v) min_v = *p; 
 59. if (*p > max_v) max_v = *p; 
 60. } 
 61. max_value = max_v; 
 62. min_value = min_v; 
 63.} 
 64. 
 65.void solve_2b(const int arr[], const size_t len, int& min_value, int& max_value) 
 66.{ 
 67. int max_v = arr[0], min_v = arr[0]; 
 68. for (const int *p = arr + 1; p < arr + len; ++p) { 
 69. if (*p < min_v) min_v = *p; 
 70. else if (*p > max_v) max_v = *p; 
 71. } 
 72. max_value = max_v; 
 73. min_value = min_v; 
 74.} 
 75. 
 76.void solve_3a(const int arr[], const size_t len, int& min_value, int& max_value) 
 77.{ 
 78. // int min_v = std::numeric_limits<int>::max(); 
 79. // int max_v = std::numeric_limits<int>::min(); 
 80. // const int *low = arr - 1; 
 81. // const int *high = arr + len; 
 82. 
 83. const int *low = arr; 
 84. const int *high = arr + len - 1; 
 85. int min_v, max_v; 
 86. if (*low < *high) { min_v = *low; max_v = *high; } 
 87. else { min_v = *high; max_v = *low; } 
 88. 
 89. while (++low <= --high) { 
 90. if (*low <= *high) { 
 91. if (*low < min_v) min_v = *low; 
 92. if (*high > max_v) max_v = *high; 
 93. } else { 
 94. if (*high < min_v) min_v = *high; 
 95. if (*low > max_v) max_v = *low; 
 96. } 
 97. } 
 98. max_value = max_v; 
 99. min_value = min_v; 
 100.} 
 101. 
 102. 
 103.void solve_3b(const int arr[], const size_t len, int& min_value, int& max_value) 
 104.{ 
 105. // 长度为奇、偶数时，分别先取出1、2个元素。剩下的元素个数一定是偶数 
 106. int min_v, max_v; 
 107. size_t t = (len - 1u) % 2u; 
 108. if (arr[0] <= arr[t]) { min_v = arr[0]; max_v = arr[t]; } 
 109. else { min_v = arr[t]; max_v = arr[0]; } 
 110. 
 111. const int *p = arr + t + 1; 
 112. while (p < arr + len) { // p 和 arr + len 奇偶性始终相同 
 113. int va = *p++; 
 114. int vb = *p++; 
 115. if (va <= vb) { 
 116. if (va < min_v) min_v = va; 
 117. if (vb > max_v) max_v = vb; 
 118. } else { 
 119. if (vb < min_v) min_v = vb; 
 120. if (va > max_v) max_v = va; 
 121. } 
 122. } 
 123. 
 124. max_value = max_v; 
 125. min_value = min_v; 
 126.} 
 127. 
 128.void solve_3c(const int arr[], const size_t len, int& min_value, int& max_value) 
 129.{ 
 130. // 长度为奇、偶数时，分别先取出1、2个元素。剩下的元素个数一定是偶数 
 131. int min_v, max_v; 
 132. size_t t = (len - 1u) % 2u; 
 133. if (arr[0] <= arr[t]) { min_v = arr[0]; max_v = arr[t]; } 
 134. else { min_v = arr[t]; max_v = arr[0]; } 
 135. 
 136. 
 137. for (const int *p = arr + t + 1; p < arr + len; p += 2) { // p 和 arr + len 奇偶性始终相同 
 138. int va = *p; 
 139. int vb = *(p + 1); 
 140. if (va <= vb) { 
 141. if (va < min_v) min_v = va; 
 142. if (vb > max_v) max_v = vb; 
 143. } else { 
 144. if (vb < min_v) min_v = vb; 
 145. if (va > max_v) max_v = va; 
 146. } 
 147. } 
 148. 
 149. max_value = max_v; 
 150. min_value = min_v; 
 151.} 
 152. 
 153. 
 154.static void solve_4a_(const int arr[], size_t low, size_t high, int& min_value, int& max_value) 
 155.{ 
 156. if (high - low <= 1u) { 
 157. if (arr[low] <= arr[high]) { min_value = arr[low]; max_value = arr[high]; } 
 158. else { min_value = arr[high]; max_value = arr[low]; } 
 159. return; 
 160. } 
 161. 
 162. size_t mid = low + (high - low) / 2u; 
 163. int min_left, max_left; 
 164. solve_4a_(arr, low, mid, min_left, max_left); 
 165. 
 166. int min_right, max_right; 
 167. solve_4a_(arr, mid + 1, high, min_right, max_right); 
 168. 
 169. min_value = std::min(min_left, min_right); 
 170. max_value = std::max(max_left, max_right); 
 171.} 
 172. 
 173. 
 174.void solve_4a(const int arr[], const size_t len, int& min_value, int& max_value) 
 175.{ 
 176. return solve_4a_(arr, 0, len - 1u, min_value, max_value); 
 177.} 
 178. 
 179. 
 180.struct Range{ 
 181. int min_v, max_v; 
 182. Range(int x, int y):min_v(x), max_v(y) {} 
 183.}; 
 184. 
 185. 
 186.static Range solve_4b_(const int arr[], size_t low, size_t high) 
 187.{ 
 188. if (high - low <= 1) { 
 189. if (arr[low] <= arr[high]) return Range(arr[low], arr[high]); 
 190. return Range(arr[high], arr[low]); 
 191. } 
 192. size_t mid = low + (high - low) / 2u; 
 193. Range left = solve_4b_(arr, low, mid); 
 194. Range right = solve_4b_(arr, mid + 1, high); 
 195. return Range(std::min(left.min_v, right.min_v),std::max(left.max_v, right.max_v)); 
 196.} 
 197. 
 198.void solve_4b(const int arr[], const size_t len, int& min_value, int& max_value) 
 199.{ 
 200. Range value = solve_4b_(arr, 0, len - 1); 
 201. min_value = value.min_v; 
 202. max_value = value.max_v; 
 203.} 
 204. 
 205.static void solve_4c_(const int *low, const int *high, int& min_value, int& max_value) 
 206.{ 
 207. if (high - low <= 1) { 
 208. if (*low <= *high) { min_value = *low; max_value = *high; } 
 209. else { min_value = *high; max_value = *low; } 
 210.return; 
 211. } 
 212. const int *mid = low + (high - low) / 2u; 
 213. int min_left, max_left; 
 214. solve_4c_(low, mid, min_left, max_left); 
 215. 
 216. int min_right, max_right; 
 217. solve_4c_(mid + 1, high, min_right, max_right); 
 218. 
 219. min_value = std::min(min_left, min_right); 
 220. max_value = std::max(max_left, max_right); 
 221.} 
 222. 
 223. 
 224.void solve_4c(const int arr[], const size_t len, int& min_value, int& max_value) 
 225.{ 
 226. return solve_4c_(arr, arr + len - 1, min_value, max_value); 
 227.} 
 228. 
 229. 
 230.static Range solve_4d_(const int *low, const int *high) 
 231.{ 
 232. if (high - low <= 1) { 
 233. if (*low <= *high) return Range(*low, *high); 
 234. return Range(*high, *low); 
 235. } 
 236. const int* mid = low + (high - low) / 2u; 
 237. Range left = solve_4d_(low, mid); 
 238. Range right = solve_4d_(mid + 1, high); 
 239. return Range(std::min(left.min_v, right.min_v),std::max(left.max_v, right.max_v)); 
 240.} 
 241. 
 242.void solve_4d(const int arr[], const size_t len, int& min_value, int& max_value) 
 243.{ 
 244. Range value = solve_4d_(arr, arr + len - 1); 
 245. min_value = value.min_v; 
 246. max_value = value.max_v; 
 247.} 
 248. 
 249. 
 250. 
 251. 
 252.template<typename T> 
 253.void run_test(T arr[], size_t len, int input[], size_t input_len) 
 254.{ 
 255. int min_value, max_value; 
 256. for (size_t i = 0; i < len; ++i) { 
 257. printf("%d %-20s ", i, arr[i].str); 
 258. unsigned ta = mclock(); 
 259. for (size_t j = Pack; j != 0; --j) 
 260. arr[i].func(input, input_len, min_value, max_value); 
 261. ta = mclock() - ta; 
 262. printf("min/max: %d/%d elapsed: %u ms/n", min_value, max_value, ta / Pack); 
 263. } 
 264. printf("/n"); 
 265.} 
 266. 
 267.struct Func { 
 268. void (*func)(const int arr[], const size_t len, int& min_value, int& max_value); 
 269. const char *str; 
 270.}; 
 271. 
 272.struct Generator { 
 273. int operator()() const { return (rand() << 15) + rand(); } 
 274.}; 
 275. 
 276.void test() 
 277.{ 
 278. const size_t N = Length; 
 279. if (Fix_M == 0 || N < 100) return; 
 280. const Func func[] = { 
 281. { solve_1a, " 1a 两次遍历" }, 
 282. { solve_1b, " 1b 两次遍历（优化）" }, 
 283. { solve_2a, " 2a 一次遍历" }, 
 284. { solve_2b, " 2b 一次遍历（优化）" }, 
 285. { solve_3a, " 3a 取头尾两元素" }, 
 286. { solve_3b, " 3b 取相邻两元素" }, 
 287. // { solve_3c, " 3c 取相邻两元素2" }, 
 288.#if ! TEST_CASE 
 289. { solve_4a, " 4a 分治法" }, 
 290. { solve_4b, " 4b 分治法（优化）" }, 
 291. // { solve_4c, " 4c 分治法2" }, // 
 292. // { solve_4d, " 4d 分治法（优化2）" }, // 用指针，速度会稍快点 
 293.#endif 
 294. 
 295. }; 
 296. 
 297. const size_t func_len = sizeof(func) / sizeof(func[0]); 
 298. std::vector<int> src(N); 
 299. for (size_t i = 0; i < N; ++i) src[i] = i; 
 300. 
 301.#if ! TEST_CASE 
 302. printf(" 递增 pos: 0 len:%u/n", N); 
 303. run_test(func, func_len, &src[0], N); 
 304. for (size_t i = 0; i < N; ++i) src[i] = N - i; 
 305. printf(" 递减 pos: 0 len:%u/n", N); 
 306. run_test(func, func_len, &src[0], N); 
 307.#endif 
 308. 
 309. // srand(time(NULL)); 
 310. 
 311. for (unsigned i = 0; i < Fix_M; ++i) { 
 312. #if RANDOM_SHUFFLE 
 313. std::random_shuffle(src.begin(), src.end()); 
 314. #else 
 315. std::generate(src.begin(), src.end(), Generator()); 
 316. #endif 
 317. printf (" 乱序%d pos: 0 len %u/n", i + 1, N); 
 318. run_test(func, func_len, &src[0], N); 
 319. } 
 320. 
 321.#if TEST_RAND_POS 
 322. const unsigned sub_len = N / 4u; 
 323. const unsigned max_pos = N - sub_len; 
 324. for (unsigned i = 0; i < Rand_M; ++i) { 
 325. size_t pos = rand() % max_pos; 
 326. printf (" 乱序 pos: %u len %u/n", pos, sub_len); 
 327. run_test(func, func_len, &src[pos], sub_len); 
 328. } 
 329.#endif 
 330. 
 331.} 
 332. 
 333. 
 334.int main() 
 335.{ 
 336. const HANDLE handle = GetCurrentProcess(); 
 337. SetPriorityClass(handle, REALTIME_PRIORITY_CLASS); 
 338. SYSTEM_INFO info; 
 339. GetSystemInfo(&info); 
 340. const int num = info.dwNumberOfProcessors; 
 341. if (num > 1) SetProcessAffinityMask(handle, num); 
 342. test(); 
 343.}

转载自：[http://blog.csdn.net/flyinghearts/article/details/6388834][http_blog.csdn.net_flyinghearts_article_details_6388834]\#

[0_1304436412234Q.gif]: /images/20220515/e7aea9f5e902463a99ba42fb8cb80376.png
[0_13044364475NMv.gif]: /images/20220515/1e562b6b59f64b7493ea4b45ae837711.png
[http_blog.csdn.net_flyinghearts_article_details_6388834]: http://blog.csdn.net/flyinghearts/article/details/6388834