reference：排序算法参考《数据结构》严蔚敏（清华大学出版社）
首先是最经典的冒泡排序void poposort(int a[],int n)
{
int i,j;
for(i=0;ia[j+1])
{
int temp;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
快速排序
void qsort(int a[],int min,int max)
{
int key=a[min];//将基准数定为第一个数
int start=min,end=max;//这一部分的开端和结尾下标
int temp;
while(end>start)
{
while(end>start&&a[end]>=key)
end--;//从尾开始，如果后面是大数，end向前进，走不动了停止
if(a[end]
temp=a[end];
a[end]=a[start];
a[start]=temp;
}//如果停止位置数小于key则交换
while(end>start&&a[start]<=key)
start++;//从头开始，如果后面是小数，start向后走，走不动了停止前进
if(a[start]>key)
{
temp=a[start];
a[start]=a[end];
a[end]=temp;
}//如果停止位置大于key则交换
}//如果end是大于start的，说明这趟数没有走完，继续走，如果走完了，说明成功将数分为了大小两部分
if(start>min)
{
qsort(a,min,start-1);//前一部分排序
}
if(end
qsort(a,end+1,max);//后一部分排序
}
}//递归快速排序，如果start==end==min==max说明程序结束
直接插入排序
void insertsort(int a[],int n)
{
int i,j;
for(i=2;i<=n;i++)
if(a[i]
a[0]=a[i];//a[0]作为存储小数的空间来用
a[i]=a[i-1];
for(j=i-2;a[0]
a[j+1]=a[j];
}//后面数向前移动，方便插入
a[j+1]=a[0];//插入的步骤
}
}//每次找一部分，然后把最后一个数按顺序插入，其中插入可以用折半插入
折半插入排序
void zhebaninsertsort(int a[],int n)
{
int key;
int i,j;
int low,high,mid;
for(i=1;i
key=a[i];
low=0;
high=i-1;
while(low<=high)
{
mid=(low+high)/2;
if(keyhigh+1;j--)
a[j]=a[j-1];
a[high+1]=key;
}
}//每次找一部分，然后把最后一个数按顺序插入，其中插入可以用折半插入
选择排序
int selectminikey(int a[],int k,int n)
{
int min=a[k];
int i;
int key;
for(i=k;i
min=a[i];
key=i;
}
return key;
}//选择最小数
void selectsort(int a[],int n)
{
int i,j;
for(i=0;i
j=selectminikey(a,i,n);
if(i!=j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}//每次都选择最小的和当前的坐标比，如果当前不是最小则交换
基数排序
void radixsort(int a[],int n)
{
int *b;
int radix=1;//作基数
int i,j,k;
b=(int *)malloc(n*sizeof(int));
for(k=0;k<=5;k++)
{//这里最大能排到第6位数
int bucket[base]={0};//作计数器
for(i=0;i//统计每个桶中的记录数
j=(a[i]/radix)%base;
bucket[j]++;
//printf("%d ",bucket[(a[i]/exp)%base]);
}
//printf("n");
for(i=1;i
bucket[i]+=bucket[i-1];
//printf("%d ",bucket[i]);
}
//printf("n");
for(i=n-1;i>=0;i--)
b[--bucket[(a[i]/radix)%base]]=a[i];
for (i=0;i
归并排序
void merge(int sr[],int tr[],int i,int m,int n)
{
int j,k;
for(k=i,j=m+1;i<=m&&j<=n;k++)//tr数组从i开始计数，i，j表示两部分分别的坐标
{
if(sr[i]//将sr[s..t]归并排序为tr1[s..t]
int m;
int tr2[100000];
if(s==t)
tr1[t]=sr[s];
else
{//如果头坐标不等于尾坐标
m=(s+t)/2;//分为两部分分别排序
mergesort(sr,tr2,s,m);
mergesort(sr,tr2,m+1,t);
merge(tr2,tr1,s,m,t);//两部分归并，排序的主要部分
}
}
堆排序
{//已知a[s..m]中记录的关键字除a[s]之外均满足堆的定义，本函数
//调整a[s]关键字,使a[s..m]成为一个大顶堆(对其中记录的关键字而言)
int j;
int ac=a[s];
for(j=2*s;j<=m;j*=2)
{// 沿值较大的孩子结点向下筛选
if(j=a[j])
break;// ac应插入在位置s上
a[s]=a[j];
s=j;
}
a[s]=ac;// 插入
//for(int i=1;i<=10;i++)
// printf("%d ",a[i]);
//printf("n");
}
void heapsort(int a[],int length)
{
int i;
int temp;
for(i=length/2;i>0;i--)
heapadjust(a,i,length);
for(i=length;i>1;i--)
{
temp=a[i];
a[i]=a[1];
a[1]=temp;
heapadjust(a,1,i-1);// 将a[1..i-1]重新调整为大顶堆
}
}
希尔排序
void shellsort(int a[],int n)
{
int gap=n/2;
int i,j;
int temp;
while(gap>0)
{
for(i=gap;i//i为这组数第二个数的坐标，每一次前进一个数，分别和前面数作比较
temp=a[i];
for(j=i-gap;j>=0&&temp//如果temp>a[j]就不用再比较了，省时间
a[j+gap]=a[j];
}
a[j+gap]=temp;
}
gap/=2;
}
}
测试函数
int main()
{
int n;
int *a,*b;
int i;
printf("请输入您数据的个数：");
scanf("%d",&n);
printf("请输入您的数据：");
a=(int *)malloc((n)*sizeof(int));
b=(int *)malloc((n+1)*sizeof(int));
for(i=0;i
printf("堆排序结果：");
for(i=1;i<=n;i++)
b[i]=a[i-1];
heapsort(b,n);
for(i=0;i
printf("归并排序结果：");
for(i=1;i<=n;i++)
b[i]=a[i-1];
mergesort(b,b,1,n);
for(i=0;i
printf("基数排序结果：");
for(i=0;i
printf("快速排序结果：");
for(i=0;i
printf("起泡排序结果：");
for(i=0;i
printf("希尔排序结果：");
for(i=0;i
printf("选择排序结果：");
for(i=0;i
printf("直接插入排序结果：");
for(i=0;i
printf("折半插入排序结果：");
for(i=0;i 
