编程之美4：求数组中的最大值和最小值

桃扇骨 2022-06-11 05:54 259阅读 0赞

**方法1**：暴力方法 遍历一遍数组，比较2\*N次求出最大值和最小值

**方法2**：改进方法 （破坏了原数组）  
            遍历一遍数组使得**下标为偶数的元素较下标为奇数的元素大**,再分别求出最大值和最小值  
            比较次数为3\*N/2次

**方法3**：改进方法 （不破坏原数组）  
             遍历一遍数组**将相邻元素中较大值和nMax比较,将较小值和nMin比较**  
             比较次数为3\*N/2次

**方法4**：改进方法   
            **分治思想**，先分别求出前半部分和后半部分数组的最大值和最小值，  
            然后两部分中的最大值和最小值分别比较求出整个数组的最大值和最小值  
            比较次数为3\*N/2-2次

**代码如下：**

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  // 求数组中的最大值最小值.cpp : 定义控制台应用程序的入口点。  
2.  \#include "stdafx.h"  
3.  \#include <iostream>  
4.  **using** **namespace** std;  
5.    
6.  //方法一：暴力方法 遍历一遍数组，比较2\*N次求出最大值和最小值  
7.  **void** FindMaxAndMinMethod1(**int** \*pArr, **int** nLength, **int** &nMax, **int** &nMin)  
8.  \{  
9.      **if** (pArr == NULL || nLength <= 0)  
10.     \{  
11.         cout << "输入有误！" << endl;  
12.         **return**;  
13.     \}  
14.   
15.     nMax = pArr\[0\];  
16.     nMin = pArr\[0\];  
17.     **for** (**int** i=1; i<nLength; i++)  
18.     \{  
19.         **if** (nMin > pArr\[i\])  
20.         \{  
21.             nMin = pArr\[i\];  
22.         \}  
23.   
24.         **if** (nMax < pArr\[i\])  
25.         \{  
26.             nMax = pArr\[i\];  
27.         \}  
28.     \}  
29. \}  
30.   
31.   
32. //方法二：改进方法 （破坏了原数组）  
33. //遍历一遍数组使得下标为偶数的元素较下标为奇数的元素大,再分别求出最大值和最小值  
34. //比较次数为3\*N/2次  
35. **void** FindMaxAndMinMethod2(**int** \*pArr, **int** nLength, **int** &nMax, **int** &nMin)  
36. \{  
37.     **if** (pArr != NULL && nLength > 0)  
38.     \{  
39.         **if** (nLength == 1)//数组只有一个元素  
40.         \{  
41.             nMax = pArr\[0\];  
42.             nMin = pArr\[0\];  
43.             **return**;  
44.         \}  
45.   
46.         **if** (nLength == 2)//数组只有两个元素  
47.         \{  
48.             **if** (pArr\[0\] > pArr\[1\])  
49.             \{  
50.                 nMax = pArr\[0\];  
51.                 nMin = pArr\[1\];  
52.             \}  
53.             **else**  
54.             \{  
55.                 nMax = pArr\[1\];  
56.                 nMin = pArr\[0\];  
57.             \}  
58.             **return**;  
59.         \}  
60.   
61.         //遍历一遍数组使得下标为偶数的元素较下标为奇数的元素大  
62.         **for** (**int** i=0; i<nLength; i+=2)  
63.         \{  
64.             **if** (i+1 < nLength && pArr\[i\] < pArr\[i+1\])  
65.             \{  
66.                 **int** nTemp = pArr\[i\];  
67.                 pArr\[i\] = pArr\[i+1\];  
68.                 pArr\[i+1\] = nTemp;  
69.             \}  
70.         \}  
71.   
72.         //求最大值  
73.         nMax = pArr\[0\];  
74.         **for** (**int** j=2; j<nLength; j+=2)  
75.         \{  
76.             **if** (nMax < pArr\[j\])  
77.             \{  
78.                 nMax = pArr\[j\];  
79.             \}  
80.         \}  
81.   
82.         //求最小值  
83.         nMin = pArr\[1\];  
84.         **for** (**int** t=3; t<nLength; t+=2)  
85.         \{  
86.             **if** (nMin > pArr\[t\])  
87.             \{  
88.                 nMin = pArr\[t\];  
89.             \}  
90.         \}  
91.     \}     
92. \}  
93.   
94. //方法三：改进方法 （不破坏原数组）  
95. //遍历一遍数组将相邻元素中较大值和nMax比较,将较小值和nMin比较  
96. //比较次数为3\*N/2次  
97. **void** FindMaxAndMinMethod3(**int** \*pArr, **int** nLength, **int** &nMax, **int** &nMin)  
98. \{  
99.     **if** (pArr != NULL && nLength > 0)  
100.     \{  
101.         **if** (nLength == 1)//数组只有一个元素  
102.         \{  
103.             nMax = pArr\[0\];  
104.             nMin = pArr\[0\];  
105.             **return**;  
106.         \}  
107.   
108.         **if** (nLength == 2)//数组只有两个元素  
109.         \{  
110.             **if** (pArr\[0\] > pArr\[1\])  
111.             \{  
112.                 nMax = pArr\[0\];  
113.                 nMin = pArr\[1\];  
114.             \}  
115.             **else**  
116.             \{  
117.                 nMax = pArr\[1\];  
118.                 nMin = pArr\[0\];  
119.             \}  
120.             **return**;  
121.         \}  
122.   
123.         //初始赋值  
124.         **if** (pArr\[0\] > pArr\[1\])  
125.         \{  
126.             nMax = pArr\[0\];  
127.             nMin = pArr\[1\];  
128.         \}  
129.         **else**  
130.         \{  
131.             nMax = pArr\[1\];  
132.             nMin = pArr\[0\];  
133.         \}  
134.   
135.         **for** (**int** i=2; i<nLength; i+=2)  
136.         \{  
137.             **if** (i+1 < nLength && pArr\[i\] < pArr\[i+1\])  
138.             \{  
139.                 **if** (nMax < pArr\[i+1\])//将较大值和nMax比较  
140.                 \{  
141.                     nMax = pArr\[i+1\];  
142.                 \}  
143.   
144.                 **if** (nMin > pArr\[i\])//将较小值和nMin比较  
145.                 \{  
146.                     nMin = pArr\[i\];  
147.                 \}  
148.             \}  
149.             **else** **if** (i+1 < nLength && pArr\[i\] > pArr\[i+1\])  
150.             \{  
151.                 **if** (nMax < pArr\[i\])//将较大值和nMax比较  
152.                 \{  
153.                     nMax = pArr\[i\];  
154.                 \}  
155.   
156.                 **if** (nMin > pArr\[i+1\])//将较小值和nMin比较  
157.                 \{  
158.                     nMin = pArr\[i+1\];  
159.                 \}  
160.             \}  
161.             **else**//最后剩下一个元素  
162.             \{  
163.                 **if** (nMax < pArr\[i\])  
164.                 \{  
165.                     nMax = pArr\[i\];  
166.                 \}  
167.   
168.                 **if** (nMin > pArr\[i\])  
169.                 \{  
170.                     nMin = pArr\[i\];  
171.                 \}  
172.             \}  
173.         \}         
174.     \}     
175. \}  
176.   
177. //方法四：改进方法   
178. //分治思想，先分别求出前半部分和后半部分数组的最大值和最小值，  
179. //然后两部分中的最大值和最小值分别比较求出整个数组的最大值和最小值  
180. //比较次数为3\*N/2-2次  
181. **void** FindMaxAndMinMethod4(**int** \*pArr, **int** nStart, **int** nEnd, **int** &nMax, **int** &nMin)  
182. \{  
183.     **if** (nEnd - nStart <= 1)  
184.     \{  
185.         **if** (pArr\[nStart\] > pArr\[nEnd\])  
186.         \{  
187.             nMax = pArr\[nStart\];  
188.             nMin = pArr\[nEnd\];  
189.         \}  
190.         **else**  
191.         \{  
192.             nMax = pArr\[nEnd\];  
193.             nMin = pArr\[nStart\];  
194.         \}  
195.         **return**;  
196.     \}  
197.   
198.     **int** nLeftMax = 0;  
199.     **int** nLeftMin = 0;  
200.     **int** nRightMax = 0;  
201.     **int** nRightMin = 0;  
202.     FindMaxAndMinMethod4(pArr, nStart, nStart+(nEnd-nStart)/2, nLeftMax, nLeftMin);  
203.     FindMaxAndMinMethod4(pArr, nStart+(nEnd-nStart)/2+1, nEnd, nRightMax, nRightMin);  
204.       
205.     nMax = nLeftMax > nRightMax ? nLeftMax : nRightMax;  
206.     nMin = nLeftMin < nRightMin ? nLeftMin : nRightMin;    
207. \}  
208.   
209. **int** \_tmain(**int** argc, \_TCHAR\* argv\[\])  
210. \{  
211.     //int nArr\[1\] = \{-4\};  
212.     //int nArr\[2\] = \{-4,-1\};  
213.     //int nArr\[3\] = \{-4,-1,0\};  
214.     **int** nArr\[5\] = \{-4,-1,0, 8,9\};  
215.     **int** max = 0;  
216.     **int** min = 0;  
217.     FindMaxAndMinMethod1(nArr, 5, max, min);  
218.     cout << "最大值为：" << max << " 最小值为：" << min << endl;  
219.     max = 0;  
220.     min = 0;  
221.     FindMaxAndMinMethod2(nArr, 5, max, min);  
222.     cout << "最大值为：" << max << " 最小值为：" << min << endl;  
223.     max = 0;  
224.     min = 0;  
225.     FindMaxAndMinMethod3(nArr, 5, max, min);  
226.     cout << "最大值为：" << max << " 最小值为：" << min << endl;  
227.     max = 0;  
228.     min = 0;  
229.     FindMaxAndMinMethod4(nArr, 0, 4, max, min);  
230.     cout << "最大值为：" << max << " 最小值为：" << min << endl;  
231.     system("pause");  
232.     **return** 0;  
233. \}

运行结果：

![SouthEast][]

来自：[http://blog.csdn.net/htyurencaotang/article/details/12437335][http_blog.csdn.net_htyurencaotang_article_details_12437335]

[view plain]: http://blog.csdn.net/htyurencaotang/article/details/12437335#
[SouthEast]: /images/20220611/8500559ca0de47eaa3787bb2f29c77f1.png
[http_blog.csdn.net_htyurencaotang_article_details_12437335]: http://blog.csdn.net/htyurencaotang/article/details/12437335