排序的模板

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4 + 2;
int n, a[maxn];

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-')
		{
			f = -1;
		}
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch^48);
		ch = getchar();
	}
	return x = f;
}
//快速排序 
void qsort(int l, int r)
{
	int i, j, mid, p;
	i = l, j = r;
	mid = a[(l+r)/2];
	do
	{
		while(a[i] < mid) i++;
		while(a[j] > mid) j++;
		if(i <= j)
		{
			p = a[i]; a[i] = a[j]; a[j] = p;
			i++; j--;
		}
	}while(i <= j);
	if(l < k) qsort(l, j);
	if(i < r) qsort(i, r);
}

//归并排序
void msort(int s, int t)
{
	if(s == t) return;
	int mid = (l + r) / 2;
	msort(s, mid);
	msort(mid+1, t);
	int i=s, j=mid+1, k=s;
	while(i <= mid && j <= t)
	{
		if(a[i] <= a[j])
		{
			r[k] = a[i]; k++; i++;
		}
		else 
		{
			r[k] = a[j]; k++; j++;
		}
	}
	while(i <= mid)
	{
		r[k] = a[i]; k++; i++;
	}
	while(j <= mid)
	{
		r[k] = a[j]; k++; j++:
	}
	for(int i=s; i<=t; i++) a[i] = r[i];
} 

//归并排序求逆序对
void msort(int s, int t)
{
	if(s == t) return;
	int mid = (s + t) / 2;
	msort(s, mid);
	msort(mid+1, t);
	int i=s, j = mid+1, k = s;
	while(i <= mid && j <= t)
	{
		if(a[i] <= a[j])
		{
			r[k] = a[i]; k++; j++;
		}
		else 
		{
			r[k] = a[j]; k++; j++;
			ans += mid - i + 1;
		}
	}
	//当然，这两个循环不会都进入 
	while(i <= mid)
	{
		r[k] = a[i]; k++; i++;
	}
	while(j <= t)
	{
		r[k] = a[j]; k++; j++;
	}
	for(int i=s; i<=t; i++) a[i] = r[i];
} 

//堆排序1
void swap(int &a, int &b)
{
	int t = a; a = b; b = t;
}

void put(int d)
{
	int now, next;
	heap[++heap_size] = d;
	now = heap_size;
	while(now > 1)
	{
		next = now >> 1;
		if(heap[now] >= heap[next]) return;
		swap(heap[now], heap[next]);
		now = next;
	 } 
 } 
 
 int get()
 {
 	int now, next, res;
 	res = heap[1];
 	heap[1] = heap[heap_size--];
 	now = 1;
 	while(now*2 <= heap_size)
 	{
 		next = now * 2;
 		if(next < heap_size && heap[next+1] < heap[next]) next++;
 		if(heap[now] <= heap[next]) return res;
 		swap(heap[now, heap[next]]);
 		now = next;
	 }
	 return res;
 }
 
 //堆排序2 感觉还是第一种好理解，我就不求甚解了吧。。。 
void heap(int r[], int nn, int ii)
{
 	int x, i = ii, j;
 	x = r[ii];
 	j = 2 * i;
 	while(j <= nn)
 	{
 		if(j < nn && r[j] < t[j+1]) j++;
 		if(x < r[j])
 		{
 			r[i] = r[j]; i = j; j = 2*i;
		}
		else j = nn + 1;
	}
	r[i] = x;
} 

int main() 
{
	//选择排序 
	n = read();
	for(int i=1; i<=n; i++) a[i] = read();
	for(int i=1; i<=n; i++)
	{
		k = i;
		for(int j=i+1; j<=n; j++)
		{
			if(a[j] < a[k]) k = j;
		}
		if(k != i)
		{
			tmp = a[i]; a[i] = a[k]; a[k] = tmp;
		}
	}
	for(int i=1; i<=n; i++)
	{
		printf("%d ", a[i]);
	}
	//冒泡排序
	bool ok;
	for(int i=n; i>1; i--)
	{
		ok = true;
		for(int j=1; j<i; j++)
		{
			if(a[j] > a[j+1])
			{
				swap(a[j], a[j+1]);
				ok = false;
			}
		}
		if(ok == true) break;
	}
	//车厢重组
	n = read();
	for(int i=1; i<=n; i++) a[i] = read();
	for(int i=1; i<=n-1; i++)
	{
		for(int j=1; j<=n-i; j++)
		{
			if(a[j] > a[j+1])
			{
				swap(a[j], a[j+1]);
				s++;
			}
		}
	}
	printf("%d", s);
	//插入排序
	n = read();
	for(int i=1; i<=n; i++) a[i] = read();
	for(int i=1; i<=n; i++)
	{
		for(int j=i-1; j>=1; j--)
		{
			if(a[j] < a[i]) break;
		}
		if(j != i-1)
		{
			tmp = a[i];
			for(int k=i-1; k>j; k--)
			{
				a[k+1] = a[k];
			}
			a[j+1] = tmp;
		}
	}
	//桶排序
	int b[101], n;
	memset(b, 0, sizeof(b));
	n = read();
	for(int i=1; i<=n; i++)
	{
		k = read(); b[k]++;
	} 
	for(int i=0; i<=100; i++)
	{
		while(b[i] > 0)
		{
			printf("%d "); b[i]--;
		}
	}
	//计数排序：和桶排序挺相似的？
	//明明的随机数
	n = read();
	for(int i=1; i<=n; i++)
	{
		int x = read();
		if(b[x] == 0) m++;
		b[x]++;
	} 
	cout << m << endl;
	for(int i=0; i<=1000; i++)
	{
		if(b[i] > 0) cout << i << " ";
	}
	cout << endl;
	//快速排序
	n = read();
	for(int i=1; i<=n; i++) a[i] = read(); 
	qsort(1, n);
	for(int i=1; i<=n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	//堆排序
	n = read();
	for(int i=1; i<=n; i++) 
	{
		x = read();
		put(x);
	}
	for(int i=1; i<n; i++) cout << get() << " ";
	cout << get() << endl;
	//堆排序2
	for(int i=n/2; i>=1; i--) heap(a, n, i);
	for(int i=n; i>=2; i--)
	{
		swap(a[1], a[i]);
		heap(a, i-1, 1);
	 } 
	
	return 0;
}