#include 
#include 

using namespace std;

// 插入排序
void InsertSort(vector &data)
{
	for (int i=1; i!=data.size(); ++i)
	{
		int key = data[i];			// 暂存第i个元素的值。
		int j = i-1;
		while (j>=0 && data[j]>key)	// 第 i 个元素之前的所有元素已经完成排序，只需向前寻找第一个小于key的元素的位置。
		{
			data[j+1] = data[j];	// 对于值大于key的元素，向后移动一位。
			--j;
		}
		data[j+1] = key;
	}
}

// 显示数组内容
void DisplayIntVector(const vector &data)
{
	for (int i=0; i!=data.size(); ++i)
	{
		cout << data[i] << " ";
	}
	cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	vector data;
	data.push_back(8);
	data.push_back(2);
	data.push_back(4);
	data.push_back(9);
	data.push_back(3);
	data.push_back(6);

	DisplayIntVector(data);

	InsertSort(data);
	DisplayIntVector(data);

	return 0;
}