各种排序算法的实现(C语言实现)

/* * 各种基本排序算法实现(以由小到大为例) */#include<stdio.h>#define ARRAY_LENGTH 50 //插入排序void inseartSort(int a[],int length){int i,j,index,temp;for(i=0;i<length;i++){//数组a中元素逐个有序插入数组afor(j=0;j<i;j++) //寻找第i个元素的插入位置if(a[i]<a[j])break;index=j;temp=a[i];for(j=i;j>index;j--)//移位a[j]=a[j-1];a[index]=temp;}}//快速排序void quickSort(int a[],int length){    int i=0,j=length-1; //i指向数组头元素，j指向数组尾元素int index=0;     //指向中间值int m=0;         //双向搜索，判断是i加还是j减if(length<=0)return;while(i<=j){ //一趟快速排序if(!m){            if(a[j]<a[index]){//交换a[j]和a[index]    a[j]=a[index]+a[j];    a[index]=a[j]-a[index];    a[j]=a[j]-a[index];     index=j;m=1;}        j--;}else{if(a[i]>a[index]){    a[i]=a[index]+a[i];    a[index]=a[i]-a[index];    a[i]=a[i]-a[index];     index=i;m=0;}i++;}}quickSort(a,index);quickSort(a+index+1,length-index-1);}//希尔排序void shellSort(int a[],int length){int b[ARRAY_LENGTH]; //辅助数组int d,k,j,i;d=length/2;          //增量while(d>0){for(k=0;k<d;k++){j=0;for(i=k;i<length;i+=d)//把a中要排序的元素复制到b数组b[j++]=a[i];inseartSort(b,j);j=0;for(i=k;i<length;i+=d)//把排好序的元素放回a数组a[i]=b[j++];}if(d==1)//增量为1，最后一趟插入排序排完    break;d/=2;if(d==0)d=1;}}//归并排序void mergeSort(int a[],int length){int d=2,i; //d为归并的子列中每一个子列包含的元素个数while(d<length){for(i=0;i+d<=length;i+=d) //一趟归并inseartSort(a+i,d);d*=2;}//收尾处理，因为可能有没处理完的子列(这个子列的元素个数小于d)inseartSort(a,length); }//基数排序void radixSort(int a[],int length){int b[ARRAY_LENGTH]; //存放a中元素取出的各个位数上的数字int i,index,j,temp,step=1;    for(i=0;i<length;i++)//a中各个元素复制到b    b[i]=a[i];    while(1){    for(i=0;i<length;i++)//取b中各个元素的个位数    b[i]=b[i]%10;    //对b数组进行排序,a数组按各个位数上的数字大小进行排序        for(i=0;i<length;i++){            index=i;    for(j=i;j<length;j++)    if(b[j]<b[index])    index=j;    temp=b[i];    b[i]=b[index];     b[index]=temp;    temp=a[i];    a[i]=a[index];    a[index]=temp;}    for(i=0;i<length;i++)    b[i]=a[i]/(10*step);    for(i=0;i<length;i++)//判断b中的元素是否全是0    if(b[i]!=0)    break;    if(i==length)//b中元素全是0    break;step*=10;}}/*********************** 以下是堆排序的实现 ***********************///筛选法调整堆,i指向要调整的元素void sift(int a[],int length,int i){int j=2*(i+1)-1;  //j指向i的左孩子int index=j;    //index指向某个元素的左右孩子中较大的一个int temp;if(j>=length) //i为叶子节点return;if(j+1<length)    index=a[j]>a[j+1]?j:j+1;if(a[i]<a[index]){//如果父亲结点小于孩子结点，交换       temp=a[i];   a[i]=a[index];   a[index]=temp;   sift(a,length,index); //可能破坏了左子树或右子树的排序，对子树进行筛选法调整}}//堆排序(大顶堆)void heapSort(int a[],int length){int i; //i指向要调整的元素，从length/2开始    int temp;//从length/2个元素开始调整堆for(i=length/2-1;i>=0;i--){        sift(a,length,i);}//取堆顶元素,最后一个元素代替第一个元素。然后调整堆 for(i=length-1;i>0;i--){temp=a[0];a[0]=a[i];a[i]=temp;sift(a,i,0);}}/*********************** 以上是堆排序的实现 ***********************/void main(){int i;int a[]={5,3,5,6,12,33,24,10,22,8};int b[10];//待排序序列printf("待排序序列：");    for(i=0;i<10;i++)b[i]=a[i];for(i=0;i<10;i++)printf("%-4d",b[i]);    printf("\n\n");//测试插入排序printf("插入排序  ：");inseartSort(b,10);for(i=0;i<10;i++)printf("%-4d",b[i]);    printf("\n\n");//测试快速排序printf("快速排序  ：");    for(i=0;i<10;i++)b[i]=a[i];quickSort(b,10);for(i=0;i<10;i++)printf("%-4d",b[i]);    printf("\n\n");//测试希尔排序printf("希尔排序  ：");    for(i=0;i<10;i++)b[i]=a[i];shellSort(b,10);for(i=0;i<10;i++)printf("%-4d",b[i]);    printf("\n\n");//测试归并排序printf("归并排序  ：");    for(i=0;i<10;i++)b[i]=a[i];mergeSort(b,10);for(i=0;i<10;i++)printf("%-4d",b[i]);    printf("\n\n");//测试基数排序printf("基数排序  ：");    for(i=0;i<10;i++)b[i]=a[i];radixSort(b,10);for(i=0;i<10;i++)printf("%-4d",b[i]);    printf("\n\n");//测试堆排序printf("堆排序    ：");    for(i=0;i<10;i++)b[i]=a[i];heapSort(b,10);for(i=0;i<10;i++)printf("%-4d",b[i]);    printf("\n\n");}

?