算法设计与分析（第四周）同时选最大和最小 优化解法

思路

首先把n个数分成两部分，每部分有n/2个数
然后把第一部分的数分别与第二部分对应位置的数比较，如果左边的大，就SWAP
一轮下来之后，数列被分成两半，最小数肯定在左边，最大数肯定在右边
再从左边找到最小数，从右边找到最大数

此算法可有效降低时间复杂度

运行效果

321 458 1 164 326 129 51 841 786 321 54 558 996 665 542 521 718 48 650 854 845 165 641 817 832 400 802 975 61 749 24 430 713 851 326 770 767 64 807 249 98 511 833 785 150 796 923 96 28 767 293 604 12 48 6 565 464 930 908 656 22 114 431 117 951 66 175 971 366 209 848 114 963 998 347 417 816 741 255 945 595 168 55 186 574 458 653 877 35 992 591 609 140 689 778 674 370 752 29 679
最小：1
最大：998
请按任意键继续. . .

代码

//优化解法 同时选最大和最小
#include<iostream>
#define SWAP(a,b) {int t;t=a;a=b;b=t;}
#define NUM 100//总个数
using namespace std;
int main()
{
	int a[NUM];

	//输入
	int i;
	for (i = 0; i < NUM; i++)
	{
		cin >> a[i];
	}

	//比较偶数个
	int max, min;
	for (i = 0; i < NUM / 2; i++)
	{
		if (a[i] > a[NUM / 2 + i])
		{
			SWAP(a[i], a[NUM / 2 + i]);//小的放左边
		}
	}

	//找最小
	min = a[0];
	for (i = 0; i < NUM / 2; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
	}

	//找最大
	max = a[NUM / 2];
	for (i = NUM / 2; i < NUM; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
	}

	if (NUM % 2 != 0)//奇 最后轮空
	{
		if (a[NUM - 1] < min)min = a[NUM - 1];
		if (a[NUM - 1] > max)max = a[NUM - 1];
	}

	//输出
	cout << "最小：" << min << endl;
	cout << "最大：" << max << endl;

	system("pause");
}