1 冒泡排序
排序思想：每次选出最大的放到序列末尾，序列每次去除最后的元素，直到剩下最后一个元素排序结束。
特点：在寻找本轮最大元素时可以设置一个标志位，如果一轮下来标志位没变说明所有元素都以有序。平均时间复杂度为O(n^2)。
2 插入排序
排序思想：在对第i个元素进行添加时，前面i-1个元素已经排序结束，将第i个元素插入到前面i-1个元素的适当位置即可。
特点：当元素基本有序时只需要做比较和少量的换序即可。平均时间复杂度为O(n^2)。
递归实现的代码：
template<class T>
void insert_sort(T A[],int n){ if(n<1) return; insert_sort(A,n-1);int a = A[n];
int k = n-1; while(k>=0 &&A[k]>a){ A[k+1] = A[k]; k = k-1; } A[k+1] = a; // k+1恰好是空出那个元素}
3 归并排序
排序思想：长度为N的序列可以分为两个长度为N/2的序列，如果两个长度为N/2的序列已经有序，那么使用合并算法【见附录】合并即可，这样问题的规模就减小为两个长度为N/2序列的排序问题，递归即可。
特点：平均时间复杂度为O(n*logn)。
4 选择排序
排序思想：每次从待排序中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
特点： 是不稳定的排序方法，平均时间复杂度为O(n^2)。
5 堆排序
排序思想：使用待排序数据建立一个堆，堆是这样一种数据结构：所有父节点数据均大于（或小于）子节点数据。这样每次取出根节点即可获得有序序列。
特点：堆排序没有使用额外的存储空间！！平均时间复杂度是O(n^2)。
附录：
合并算法：
template <class Type>
void merge(Type A[],int p,int q,int r) { Type *bp = new Type[r-p+1]; //这种方式的缺点就是需要开辟较大的内存空间！ int i=p,j=1+q,k=0; while (i<=q && j<=r) if(A[i] <= A[j]) bp[k++] = A[i++]; else bp[k++] = A[j++]; if(i==q+1) //这里必须注意写法，不能使用< 判断，因为最后停留的位置不能确定，但是这个条件能确定 for(;j<=r;j++) bp[k++] = A[j]; else for (;i<=q;i++) bp[k++] = A[i]; k=0; for (i=p;i<=r;i++) A[i] = bp[k++]; delete bp; }
堆操作：
1 元素上移：
void shift_up(int H[],int i){
int value = H[i]; int pos = i; while(i/2 >= 1 && value > H[i/2]){ pos = i/2; H[i] = H[i/2]; i = i/2; } H[pos] = value; }2 元素下移：
void shift_down(int H[],int n,int i){
int value = H[i]; bool flag = false; int pos = i; while(i*2 <= n){ int j; if(i*2 == n) //一定要判断数组是否越界 j = i*2; else j = H[2*i] >= H[2*i+1] ? 2*i :2*i + 1; if(value<H[j]){ pos = j; H[i] = H[j]; i = j; }else{ //停止查找 break; } } H[pos] = value; //最终的位置！}3 元素插入：
void insert(int H[],int &n,int value){ //注意这里n要使用引用变量
n = n+1; H[n] = value; shift_up(H,n); }4 元素删除
void delete_i(int H[],int &n,int i){
value = H[i]; last = H[n]; n = n - 1; H[i] = last; if(last > value) shift_up(H,i); else shift_down(H,n,i); }5 删除堆顶元素
int delete_max(int H[],int &n){
int max = H[1]; delete_i(H[],n,1); return max; }堆建立：
void make_heap(int A[],int H[],int n){
int num = 0; for(i=0;i<n;i++){ insert(H,num,A[i]); } }void make_heap_self(int H[],int n){
A[n] = A[0]; //这个比较特殊。。 for(i = n/2;i>=1;i--){ shift_down(H,n,i); } }堆排序：
void heap_sort(int A[],int n){
int i; make_heap_self(A,n); for(i=n;i>1;i--){ swap(A,i,1); shift_down(A,i-1,1); }}