学步园

“星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：
“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小次序摆好——小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。
我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到最后大小有序的结果呢？”

这个问题是《编程之美》1.3章节的排序题，下面是书中解法一的实现，思路最清晰简单，同时也是最差的解法。

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

void Show(vector<int> &values)
{
	for (auto value : values)
		cout << value << " ";
	cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	// 随机生成10张饼（可能会有直径相同的饼）
	srand(time(nullptr));
	vector<int> values(10);
	for (int i = 0; i < values.size(); ++i)
		values[i] = rand() % 10;

	Show(values);
	cout << endl;

	// 最多循环n-1次就能排序好
	for (int i = 0; i < values.size() - 2; ++i)
	{
		auto maxIt = max_element(values.begin(), values.end() - i);
		if ((maxIt == values.end() - i - 1) || (*maxIt == *(values.end() - i - 1)))
			continue;

		reverse(values.begin(), maxIt + 1);
		Show(values);
		reverse(values.begin(), values.end() - i);
		Show(values);
		cout << endl;
	}

	system("pause");
	return 0;
}