分享八大排序算法，纯属自己的理解，如有错，请纠正，
只是以代码加上自己的少量注解分析八大排序算法而已，仅此而已，每种算法以相对数组下标从大到小排列的，输出是以数组下标大到小输出的，当然有很多不全面，有兴趣的自己深究。勿喷。
程序代码：#include <stdio.h> //你懂的
#include <time.h> //使用计时代码
#include <stdlib.h> //使用产生随机代码
////////直接插入排序属于稳定的排序，最坏时间复杂性为Θ(n^2)，空间复杂度为O(1)。
int insertsort(int a[],int n){
int i,j;
int b=0; //交换次数
for(i=0;i<n;i++){ // i 从 0 到 n-1
j=i+1; //j为i+1，即右边这个数据
//从大到小排序
if (a[j]>a[i]) //如果右边更大，改变顺序
{
int t=a[j]; //中间值t
//从右向左搜寻已排好的序列，如两数据逆序，则把此数据后退，数据t则待插入，直到正序就插入
while(i>=0&&t>a[i]) //特别注意此处是t,别写a[j]，因为a[j]值会变的，通过i移动了，仔细分析便可知
{
a[i+1]=a[i];
i--;
b++;
}
a[i+1]=t;//i已达最小或已经正序，插入t值
b++;
}
i=j-1;//返回刚开始i的位置，不能忘记
}
return b;
}
/////////////希尔排序又称缩小增量排序，是一种分组插入方法，比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素
int shellsort(int a[],int n){
int b=0,m=n;
while(m>1)
{
m/=2; //取得增量,便于分组比较
{
int i,j;
//从0+增量m处选取依次递增，分组比较
for (i=m;i<n;i++)
{
int t=a[i];
j=i-m; //取得相隔m的数据比较
if (t>a[j])
{
//和直接插入排序一样，从右向左如两数据逆序则数据后推，正序则插入
while(j>=0&&a[j]<t)
{
a[j+m]=a[j];
j-=m; //依次取得相同距离的数据，即分组排列
b++;
}
a[j+m]=t; //插入数据
b++;
}
}
}
}
return b;
}
////////////////冒泡排序
int bubblesort(int a[],int n){
int b=0;
int i,j;
for (i=n;i>0;i--)// i 从最右开始向左
{
int is=1;
for (j=0;j<i;j++)// j 从左向右走
//如果左数小于相邻的右数就交换，即将小数向后推，即冒泡，左数下标递增
if(a[j]<a[j+1])
{
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
is=0;
b++;
}
b++;
if(is) break;
}
return b;
}
/////////////////////快速排序，属于冒泡排序，排序过程可以递归进行
int quicksort(int a[],int left,int right){
static int bq;
int i=left,j=right;
int t=a[i]; //取得最左数据，一般数t取值最好是所有数据的大小的中值，即中位数，以使得分成差不多的两部分数
while(i<j){
//从最右数开始，依次左推，直到比较的两个数据为逆序时，将i处数据置另一数据
while((a[j]<t)&&(i<j)){
bq++;
j--;
}
if(j>i){
a[i]=a[j];
i++;
bq++;
}
//从上一部的a[i](非i++位置) 右边这个数开始，依次右推，直到比较的两个数据为逆序时，将j处数据置另一数据
while((a[i]>=t)&&(i<j)){ //注意i只增加到j-1
bq++;
i++;
}
if(i<j){
a[j]=a[i];
j--;
bq++;
}
}
a[i]=t;//i处数据为t，则已分好两部分，i之前的数都大于t，j之后的小于t
if(left<i-1) quicksort(a,left,i-1);
if(right>i+1) quicksort(a,i+1,right);
return bq;
}
//////////////////直接选择排序
int selectsort(int a[],int n){
int t,b=0;
int i,j,k;
for (i=0;i<n;i++)// i从 0 到 n-1
{
k=i; //k初始为i的位置
for (j=i+1;j<n;j++){ // j从 i+1 到 n-1
if(a[j]>a[k]) k=j; //选择最大的数并用k保存位置，即保存下标
b++;
}
//k不是i的位置就交换数据
if(k!=i){
t=a[i];
a[i]=a[k];
a[k]=t;
}
b++;
}
return b;
}
///////////////////堆排序。利用堆积树（堆）排序，大根堆和小根堆，将R[l..n]看成是一棵完全二叉树的顺序存储结构
//不稳定的排序方法。最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。辅助空间为O(1)
//理解此算法之前请先了解二叉树顺序存储结构表示或先画出二叉树
void heapadjust(int a[],int i,int n,int *bh){
int child;
int t;
for (t=a[i];2*i+1<n;i=child)//保证i节点有右儿子，t为父亲数据
{
(*bh)++;
child=2*i+1;//右儿子节点
//使父亲，左儿子，右儿子大小依次排序，未排好是会循环的
if(child<n-1&&a[child+1]<a[child])
child++;
if(t>a[child]) a[i]=a[child];
else break;
a[child]=t;
}
}
int heapsort(int a[],int n){
int i;
int bh=0;
//由于是以0开始的顺序结构节点，所以才使得n/2-1结点即i都是倒数第二层（有时在倒数第三层），且i都有右儿子
for(i=n/2-1;i>=0;i--)
heapadjust(a,i,n,&bh);//记住参数，进入函数
for(i=n-1;i>0;i--){//从最后节点依次走向根节点
//将节点数与根节点数交换，使得此数参与比较
int t=a[0];
a[0]=a[i];
a[i]=t;
bh++;
heapadjust(a,0,i,&bh);
}
return bh;
}
///////////////////归并排序.采用分治法 为稳定排序算法
void merge(int a[],int left,int mid,int right,int *bm){
int *s=new int [right+1];
int i=left;
int j=mid+1;
int k=left;
while(i<=mid&&j<=right){
//取出比较左半某一数据和右半某一数据，每次大的数据依次保存在 s 数组中
if(a[i]>=a[j]) s[k++]=a[i++];
else s[k++]=a[j++];
(*bm)++;
}
//把没有参与比较的数据(即跳出循环了)再依次存给 s 数组
while(i<=mid) {s[k++]=a[i++];(*bm)++;}
while(j<=right) {s[k++]=a[j++];(*bm)++;}
for(i=left;i<=right;i++) {a[i]=s[i];(*bm)++;}//将 s 数组顺序放回a中
delete []s;
}
int mergesort(int a[],int left,int right){
static int bm=0;
if(left<right)
{
int mid=(left+right)/2;
bm++;
mergesort(a,left,mid);
bm++;
mergesort(a,mid+1,right);
bm++;
merge(a,left,mid,right,&bm);
}
return bm;
}
///////////////////基数排序.稳定排序法、即依次比较所有数据每位数的大小，排序，有从高位开始的，也有从低位开始的
int radixsort(int a[],int n,int radixmax){
//下面所有数字即代表每位的数值，即0到9的取值
int b=0;
int i,j,k=0,m=n;//由于 a 数组的数据值在1到n之间，所以可设m最大是n，使得从高位数依次向低位数排列
int (*t)[10]=new int [n][10];//动态分配的数组，第二维即是数字是0到9的象征
int tr;
int order[10]={0};//0到9的数字个数数组，即，是0的数字的个数保存在数组order[0]中
while(m>=1){
for (i=0;i<n;i++){
tr=((a[i]/m)%10);//数字是tr
t[order[tr]][tr]=a[i];
order[tr]++;//个数加1
b++;
}
//把分类的数据按照数字 0~9 的顺序返回到a中
for (i=0;i<10;i++){
if(order[i]!=0)
for (j=0;j<order[i];j++){
a[k]=t[j][i];
k++;
b++;
}
order[i]=0;//个数重新置空
}
m/=10;//使得可以取得下一位数的数字
k=0;
}// while循环
// for(i=0;i<n;i++)
// delete []t[i];
delete []t;
return b;
}
///////////////////从最右向左打印
void output(int a[],int n){
int i=n;
while(i--) printf("%d ",a[i]);
putchar(10);
}
////////////////操作函数
void operate(int a[],int n){
int *r=new int [n];
int i;
double start,end;
int degree;
char ch;
printf("请选择排序算法: ");
scanf("%c",&ch);
switch(ch){
case '1':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=insertsort(r,n);
end=clock()/1000.0;
printf("直接插入排序所用时间:\t%lf s\n",end-start);
printf("直接插入排序交换次数:\t%d\n\n",degree);
break;
case '2':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=shellsort(r,n);
end=clock()/1000.0;
printf("希尔排序所用时间:\t%lf s\n",end-start);
printf("希尔排序交换次数:\t%d\n\n",degree);
break;
case '3':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=bubblesort(r,n);
end=clock()/1000.0;
printf("冒泡排序所用时间:\t%lf s\n",end-start);
printf("冒泡排序交换次数:\t%d\n\n",degree);
start=time(NULL);
break;
case '4':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=quicksort(r,0,n-1);
end=clock()/1000.0;
printf("快速排序所用时间:\t%lf s\n",end-start);
printf("快速排序交换次数:\t%d\n\n",degree);
break;
case '5':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=selectsort(r,n);
end=clock()/1000.0;
printf("直接选择排序所用时间:\t%lf s\n",end-start);
printf("直接选择排序交换次数:\t%d\n\n",degree);
break;
case '6':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=heapsort(r,n);
end=clock()/1000.0;
printf("堆排序所用时间: %lf s\n",end-start);
printf("堆排序交换次数: %d\n\n",degree);
break;
case '7':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=mergesort(r,0,n-1);
end=clock()/1000.0;
printf("归并排序所用时间:\t%lf s\n",end-start);
printf("归并排序交换次数:\t%d\n\n",degree);
break;
case '8':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=radixsort(r,n,10);
end=clock()/1000.0;
printf("基数排序所用时间:\t%lf s\n",end-start);
printf("基数排序交换次数:\t%d\n\n",degree);
break;
case '9':
return;
default:
printf("输入错误，请选择正确的操作！\n");
break;
}
getchar();
// output(r,n); //……如要看排序后结果可取消注释……
operate(a,n);
}
int main(){
printf("请输入要排序的个数:\t");
int n,i;
scanf("%d",&n);
getchar();
int *a=new int [n];
srand((unsigned int)time(NULL));
for(i=0;i<n;i++) a[i]=rand()%n+1;
printf("** 排序算法比较 **\n");
printf("====================================\n");
printf("== 1 --- 直接插入排序 ==\n");//插入排序
printf("== 2 --- 希尔排序 ==\n");
printf("== ==\n");
printf("== 3 --- 冒泡排序 ==\n");//交换排序
printf("== 4 --- 快速排序 ==\n");
printf("== ==\n");
printf("== 5 --- 直接选择排序 ==\n");//选择排序
printf("== 6 --- 堆排序 ==\n");
printf("== ==\n");
printf("== 7 --- 归并排序 ==\n");
printf("== ==\n");
printf("== 8 --- 基数排序 ==\n");//分配式排序
printf("== ==\n");
printf("== 9 --- 退出程序 ==\n");
printf("====================================\n");
// output(a,n); //……如要看随机数顺序可取消注释……
operate(a,n);
delete []a;
return 0;
}
