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

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

 

一道很简单的题目，一般有下面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次取平均值）

 

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

 

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

 

 

 

 

 

 

 

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

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

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

 

 

 

 

 

 

从图可以看出，改用“随机洗牌”法得到乱序数组后，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#