啊哈算法——第一章：排序

桶排序的思想应该是一个非常好理解的思想，假设对一批正整数数进行排序，这些数中最大的数为N，则创建一个[0,N]的数组A。接着输入，输入a_i，则A[a_i] ++。假如我们要输出降序排序，则从N遍历到0，如果A[i]非零，则输出i。
它的时间复杂度并不高，但是它在空间上的牺牲非常大，且局限性很大。

C语言课程上一定介绍过冒泡排序和选择排序，其思想是在某一趟中，比较某个数和它下一个数是否满足升序或降序的规则，如果不满足，则交换两个数的位置，经过N-1躺遍历，最后的输出是升序或降序的。

#include 
using namespace std;
const int maxn = 105;
int a[maxn] = {0};
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n-1;i++){
		for(int j=1;j<=n-1;j++){
			if(a[j] < a[j+1]){
				swap(a[j],a[j+1]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout< 
冒泡排序实际上可以对任何类型的数据进行排序（包块结构体），解决了桶排序在空间上的浪费，但牺牲了时间复杂度，因此我们说冒泡排序是以时间换空间。
 
快速排序：O(nlogn) 
此处不再赘述快速排序的原理，而直接贴出vector+C++STL实现的快速排序模板。
 
#include 
#include 
#include 
using namespace std;
int n;
inline bool cmp(const int &n1,const int &n2){
	return n1>n;
	vector v(n);
	for(int i=0;i>v[i];
	}
	sort(v.begin(),v.end(),cmp);
	for(int i=0;i 
排序结果：
 
 使用vector自带的begin和end指针可以对vector类进行排序，且可以在cmp函数中自定义排序方法。
 实际上，使用STL的sort()进行排序时，编译器会自动帮我们选择合适的排序方法，如归并排序（稳定的）与快速排序（不稳定的）等。因此，在程序设计竞赛中直接使用sort()方法更为妥当。对于归并排序与快速排序的原理，只需要了解即可（归并排序还可以用于计算排序过程中的交换次数，当然统计交换次数需要在归并排序的模板中，而不是在sort()中）。
 
小哼买书 
任务：排序与去重
 思路：直接使用C++STL自带的set容器（集合），set中实现了自动的排序（默认为从小到大），且每个输入set的数据仅会出现一次。
 
#include 
#include 
#include 
using namespace std;
set s;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int tmp;
		cin>>tmp;
		s.insert(tmp);
	}
//	sort(s.begin(),s.end());
	set::iterator it;
	cout< 
注意set::iterator it;it可迭代对象的建立。在遍历set型数据时，需要使用iterator可迭代对象进行遍历。