插入排序

InsertionSort.cpp

//============================================================================
// Name        : Algorithm.cpp
// Author      : Songpp
// Description : Hello World in C++, Ansi-style
//============================================================================

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

void insertion_sort(vector<int> &a);
void print(vector<int> &a);

int _tmain() {
	cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!

	vector<int> a;
	a.push_back(987);
	a.push_back(156);
	a.push_back(4);
	a.push_back(987);
	a.push_back(331);
	a.push_back(776);
	a.push_back(235);
	a.push_back(10);
	a.push_back(567);
	a.push_back(776);
	a.push_back(235);
	a.push_back(10);
	a.push_back(567);
	a.push_back(776);
	a.push_back(235);
	a.push_back(10);
	a.push_back(567);
	a.push_back(50);
	a.push_back(17);
	a.push_back(43);
	a.push_back(63);
	insertion_sort(a);
	print(a);
	return 0;
}

void print(vector<int> &a){
	for(vector<int>::size_type i = 0;i!=a.size();i++){
		cout << a[i] << endl;
	}
}

void insertion_sort(vector<int> &a){
	assert(a.size() > 1);
	cout << "a.size = " <<  a.size() << endl;
	for(vector<int>::size_type j = 1; j < a.size();++j){
		int key = a[j];
		int i = j - 1;
		while(i >= 0 && a[i] > key){
			cout << "i = " << i << endl;
			a[i+1] = a[i];
			i = i - 1;
		}
		a[i+1] = key;
	}
}