插入排序：时间复杂度最坏O(n^2)，最佳O(n)，平均O(n^2) ，空间复杂度O(1)，稳定
void insertion_sort(int a[],int n)
{
for(int i=1;i<n;++i)
{
int temp=a[i];
int j=i-1;
while(j>=0 && a[j]>temp)
{
a[j+1]=a[j];
--j;
}
a[j+1]=temp;
}
}
选择排序：时间复杂度最坏O(n^2)，最佳O(n^2)，平均O(n^2)，空间复杂度O(1)，不稳定
void selection_sort(int a[],int n)
{
for(int i=0;i<n-1;++i)
{
int min=i;
for(int j=i+1;j<n;++j)
{
if(a[j]<a[min])
min=j;
}
swap(a[i],a[min]); //交换破换了稳定性
}
}
冒泡排序：时间复杂度最坏O(n^2)，最佳O(n^2)，平均O(n^2)，空间复杂度O(1)，稳定
void buble_sort(int *a,int n)
{
for(int i=0;i<n;i++)
{
int flag=1;
for(int j=n-1;j>i;j--)
{
if(a[j]<a[j-1])
{
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
flag=0;
}
}
if(flag == 1)
break;
}
}
希尔排序：时间复杂度最坏O(n^1.5)(使用Hibbard增量，相邻增量没有公因子)，最佳O(n)，空间复杂度O(1)，不稳定
void shell_sort(int a[],int n,int gap[],int t)//按增量数组gap[t]进行shell排序
{
int i,j,k,temp;
for(k=0;k!=t;++k)
for(i=gap[k];i<n;++i)//从子数组的第2个元素开始插入排序
{
temp=a[i];
for(j=i;j>=gap[k]&&temp<a[j-gap[k]];j-=gap[k])
a[j]=a[j-gap[k]];
a[j]=temp;
}
}
合并排序：时间复杂度最坏O(nlgn)，最佳O(nlgn)，平均O(nlgn)，空间复杂度O(n)，稳定
void merge(int a[],int p,int q,int r)
{
int n1=q-p+1;
int n2=r-q;
int *L=new int[n1+1];//注意要用new!!!!
int *R=new int[n2+1];
int i,j;
for(i=0;i<n1;++i)
L[i]=a[p+i];
for(j=0;j<n2;++j)
R[j]=a[q+j+1];
int inf=9999;
L[n1]=inf;R[n2]=inf;//哨兵
int k;
for(k=p,i=0,j=0;k<=r;++k)
{
if(L[i]<=R[j])
{
a[k]=L[i];
++i;
}
else
{
a[k]=R[j];
++j;
}
}
delete L[];
delete R[];
}
void merge_sort(int a[],int p,int r)
{
if(p<r)
{
int q=(p+r)/2;
merge_sort(a,p,q);
merge_sort(a,q+1,r);
merge(a,p,q,r);
}
}
堆排序：时间复杂度最坏O(nlgn)，最佳O(nlgn)，平均O(nlgn)，空间复杂度O(1)，不稳定
void max_heapify(int a[],int i,int n)//保持最大堆的性质，O(lgn)
{
int l=2*i;
int r=2*i+1;
int max,k;
if (l<=n && a[l]>a[i])
max=l;
else max =i;
if(r<=n && a[r]>a[max])//注意是max，不是i
max=r;
if(max!=i)
{
k=a[i];
a[i]=a[max];
a[max]=k;
max_heapify(a,max,n);
}
}
void build_max_heap(int a[],int n)//将一个数组变成最大堆，O(n)
{
for(int i=n/2;i>0;--i)
max_heapify(a,i,n);
}
void heap_sort(int a[],int n)//堆排序，O(nlgn)
{
build_max_heap(a,n);
int k;
for(int i=n;i>1;--i)
{
k=a[1];
a[1]=a[i];
a[i]=k;
--n;
max_heapify(a,1,n);//交换父子结点会破坏稳定性
}
}
int heap_maximum(int a[],int n)//返回最大堆的最大值，O(1)
{
return a[1];
}
int heap_extract_max(int a[],int n)//删除并返回最大堆的最大值，O(lgn)
{
int max=a[1];
a[1]=a[n];
--n;
max_heapify(a,1,n);
return max;
}
void heap_increase_key(int a[],int i,int key)//将a[i]的值增大到key，O(lgn)
{
if (key<a[i])
cerr<<"new key is smaller than current key";//这里key的值不能小于a[i]
a[i]=key;
int k;
while(i>1&&a[i/2]<a[i])
{
k=a[i];
a[i]=a[i/2];
a[i/2]=k;
i=i/2;
}
}
void max_heap_insert(int a[],int n,int key)//将元素key插入到最大堆a[n-1]中，O(lgn)
{
a[n]=-65535;
heap_increase_key(a,n,key);
}
快速排序：时间复杂度最坏O(n^2)，最佳O(nlgn)，平均O(nlgn)，空间复杂度O(1)，不稳定
int partition(int a[],int p,int r)
{
int i,j,x,k;
x=a[r];
i=p-1;
for(j=p;j<=r-1;++j)
{
if(a[j]<=x)
{
++i;
k=a[i];
a[i]=a[j];
a[j]=k;
}
}
k=a[++i];
a[i]=a[r];
a[r]=k;//a[i]和主元交换的时候破坏稳定性
return i;
}
void quicksort(int a[],int p,int r)
{
if(p<r)
{
int q=partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
//快速排序的随机化版本
int rand_partition(int a[],int p,int r)
{
int i=rand()%(r-p+1)+p;
int k=a[i];
a[i]=a[r];
a[r]=k;
return partition(a,p,r);
}
void rand_quicksort(int a[],int p,int r)
{
if(p<r)
{
int q=rand_partition(a,p,r);
rand_quicksort(a,p,q-1);
rand_quicksort(a,q+1,r);
}
}
计数排序：时间复杂度最坏O(n)，最佳O(n)，平均O(n)，空间复杂度O(n)，稳定
void counting_sort(int a[],int b[],int n,int k)//a[n]的每个数都在0-k之间，将排序的结果存放在b[n]中
{
int i;
int *c=new int[k+1];
for(i=0;i!=k+1;++i)
c[i]=0;//先置0！！
for(i=0;i!=n;++i)
++c[a[i]];//此时c[i]包含等于i的元素个数
for(i=1;i!=k+1;++i)//从1开始
c[i]=c[i-1]+c[i];//此时c[i]包含小于或等于i的元素个数
for(i=n-1;i!=-1;--i)//从数组末尾开始循环,以保持算法稳定性！！！
{
b[--c[a[i]]]=a[i];//注意！！这里要减1，因为我们的数组是从0开始的！
}
}
void counting_sort(int a[],int n,int k)//只使用O(k)的空间，但是不稳定的计数排序
{
int i;
int *c=new int[k+1];
for(i=0;i!=k+1;++i)
c[i]=0;//先置0!
for(i=0;i!=n;++i)
++c[a[i]];//此时c[i]包含等于i的元素个数
int index=0;
for(i=0;i!=k+1;++i)
{
for(int j=0;j!=c[i];++j)
a[index++]=i;
}
}
基数排序：时间复杂度O(dn)，空间复杂度O(n)，稳定
void radix_sort(int a[],int n,int d)//每个元素都有d位数字
{
for(int v=1;v<=d;++v)
counting_sort(a,v,n,9);//对每一位采用计数排序
}
桶排序：当输入均匀分布，时间复杂度平均O(n)，空间复杂度O(n)， 稳定要看对链表的排序算法
void sort(list<float> &b)
{
list<float>::iterator it=b.begin();
++it;
while(it!=b.end())
{
float temp=*it;
list<float>::iterator ix=--it;
++it;//注意将it加回去
for(;*ix>temp&&it!=b.begin();--ix,--it)
*it=*ix;
*it=temp;
++it;
}
}
void bucket_sort(float a[],int n)//a[n]中元素均匀分布在[0,1)上
{
int i;
vector<list<float> > b(n,list<float>(1,2));//创建一个以链表为元素的容器，链表的第一个元素初始化为2(哨兵)
for(i=0;i!=n;++i)
b[int(n*a[i])].insert(b[int(n*a[i])].begin(),a[i]);//将a[i]插入b[na[i]]
for(i=0;i!=n;++i)
sort(b[i]);//对每个链表排序，也可以使用O(nlgn)的排序算法
int index=0;
for(i=0;i!=n;++i)
if(*(b[i].begin())!=2)
for(list<float>::iterator it=b[i].begin();*it!=2;++it)
a[index++]=*it;//将所有链表合并
}