数据结构算法分析C++习题7.42对分数排序（要求使用线性算法-基数排序）

const int N = 1000;

struct Frac
{
	int p;
	int q;
	int c;
	Frac(int p1, int q1): p(p1), q(q1)
	{
		c = int(double(p) / q * (N + 1) * (N + 1));
	}
};

void radixSort(vector& a, int n)
{
	vector> buckets(n);
	for (int i = 0; i < 2; i++)
	{
		for (int i = 0; i < a.size(); i++)
		{
			buckets[a[i].c % n ].push_back(std::move(a[i]));
		}
		int idx = 0;
		for (auto& thisBucket : buckets)
		{
			for (auto& x : thisBucket)
			{
				x.c = x.c / n;
				a[idx++] = std::move(x);

			}
			thisBucket.clear();
		}
	}
	
}




int main()
{
	vector frac;
	int numFrac;
	cout << "how many fractions: ";
	cin >> numFrac;
	int mole, deno;
	for (int i = 0; i < numFrac; i++)
	{
		cout << "enter the " << i << "th fractions:n molecule: ";
		cin >> mole;
		cout << "denominator: ";
		cin >> deno;
		frac.push_back(Frac(mole, deno));
	}
	radixSort(frac, N + 1);
	cout << "nSorted fractions:n";
	for (const auto& x : frac)
	{
		cout << x.p << "/" << x.q << endl;
	}
	return 0;
}