PAT1045 快速排序 （25 分）【4/6通过】

题目

代码

第二次改进
一个超时，一个错误

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct Arr
{
	long int value;
	bool flag = true;
};

int mySort(Arr a1, Arr a2)
{
	return(a1.value < a2.value);
}

int main()
{
	Arr a[100001];
	int total;
	cin >> total;

	//输入
	int i;
	long int val;
	for (i = 0; i < total; i++)
	{
		scanf("%ld",&val);
		a[i].value = val;
	}

	//遍历改flag
	int j;
	int count = total;
	for (i = 0; i < total; i++)
	{
		if (a[i].flag == true)
		{
			for (j = i; j < total; j++)
			{
				if (a[j].flag == true)
				{
					if (a[i].value > a[j].value)
					{
						if (a[i].flag == true)
						{
							a[i].flag = false;
							count--;
						}
						if (a[j].flag == true)
						{
							a[j].flag = false;
							count--;
						}
					}
				}
			}
		}
	}

	//直接在原来的数组排序
	sort(a, a + total - 1, mySort);

	cout << count << endl;
	for (i = 0; i < total; i++)
	{
		if (a[i].flag == true)
		{
			cout << a[i].value;
			count--;
			if (count != 0)
			{
				cout << ' ';
			}
		}
	}
	cout << endl;
	//system("pause");
	return 0;
}

暴力查找，超时

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
	long int a[100000];
	int total;
	cin >> total;

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

	//查找主元
	int before, after;
	vector<long int>center;

	for (i = 0; i < total; i++)//判断第i个元素是否主元
	{
		//左边小
		for (before = 0; before < i; before++)
		{
			if (a[before] > a[i])
			{
				break;
			}
		}
		//右边大
		for (after = i; after < total; after++)
		{
			if (a[after] < a[i])
			{
				break;
			}
		}
		//如果能走完两个循环，说明是主元
		if (before == i && after == total)
		{
			center.push_back(a[i]);
		}
	}

	//排序输出
	sort(center.begin(), center.end());
	int size = center.size();
	cout << size << endl;

	for (i = 0; i < size; i++)
	{
		cout << center[i];
		if (i != size - 1)cout << ' ';
	}

	cout << endl;
	system("pause");
	return 0;
}

第一次改进

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct Arr
{
	long int value;
	bool flag = true;
};

int mySort(Arr a1, Arr a2)
{
	return(a1.value < a2.value);
}

int main()
{
	Arr a[100000];
	int total;
	cin >> total;

	//输入
	int i;
	long int val;
	for (i = 0; i < total; i++)
	{
		cin >> val;
		a[i].value = val;
	}

	//遍历改flag
	int j;
	for (i = 0; i < total; i++)
	{
		if (a[i].flag == true)
		{
			for (j = i; j < total; j++)
			{
				if (a[j].flag == true)
				{
					if (a[i].value > a[j].value)
					{
						a[i].flag = false;
						a[j].flag = false;
					}
				}
			}
		}
	}

	//直接在原来的数组排序
	sort(a, a + total, mySort);

	//输出
	int count = 0;
	for (i = 0; i < total; i++)
	{
		if (a[i].flag == true)
		{
			count++;
		}
	}

	cout << count << endl;
	for (i = 0; i < total; i++)
	{
		if (a[i].flag == true)
		{
			cout << a[i].value;
			count--;
			if (count != 0)
			{
				cout << ' ';
			}
		}
	}
	cout << endl;
	//system("pause");
	return 0;
}