各种排序算法的实现(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<a)break;index=j;temp=a;for(j=i;j>index;j--)//移位a=a;a=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<a){//交换a和a a=a+a; a=a-a; a=a-a; index=j;m=1;} j--;}else{if(a>a){ a=a+a; a=a-a; a=a-a; index=i;m=0;}i++;}}quickSort(a,index);quickSort(a+index+1,length-index-1);}//希尔排序void shellSort(int a[],int length){int b; //辅助数组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=a;inseartSort(b,j);j=0;for(i=k;i<length;i+=d)//把排好序的元素放回a数组a=b;}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; //存放a中元素取出的各个位数上的数字int i,index,j,temp,step=1; for(i=0;i<length;i++)//a中各个元素复制到b b=a; while(1){ for(i=0;i<length;i++)//取b中各个元素的个位数 b=b%10; //对b数组进行排序,a数组按各个位数上的数字大小进行排序 for(i=0;i<length;i++){ index=i; for(j=i;j<length;j++) if(b<b) index=j; temp=b; b=b; b=temp; temp=a; a=a; a=temp;} for(i=0;i<length;i++) b=a/(10*step); for(i=0;i<length;i++)//判断b中的元素是否全是0 if(b!=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>a?j:j+1;if(a<a){//如果父亲结点小于孩子结点,交换 temp=a; a=a; a=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;a=a;a=temp;sift(a,i,0);}}/*********************** 以上是堆排序的实现 ***********************/void main(){int i;int a[]={5,3,5,6,12,33,24,10,22,8};int b;//待排序序列printf("待排序序列:"); for(i=0;i<10;i++)b=a;for(i=0;i<10;i++)printf("%-4d",b); printf("\n\n");//测试插入排序printf("插入排序:");inseartSort(b,10);for(i=0;i<10;i++)printf("%-4d",b); printf("\n\n");//测试快速排序printf("快速排序:"); for(i=0;i<10;i++)b=a;quickSort(b,10);for(i=0;i<10;i++)printf("%-4d",b); printf("\n\n");//测试希尔排序printf("希尔排序:"); for(i=0;i<10;i++)b=a;shellSort(b,10);for(i=0;i<10;i++)printf("%-4d",b); printf("\n\n");//测试归并排序printf("归并排序:"); for(i=0;i<10;i++)b=a;mergeSort(b,10);for(i=0;i<10;i++)printf("%-4d",b); printf("\n\n");//测试基数排序printf("基数排序:"); for(i=0;i<10;i++)b=a;radixSort(b,10);for(i=0;i<10;i++)printf("%-4d",b); printf("\n\n");//测试堆排序printf("堆排序 :"); for(i=0;i<10;i++)b=a;heapSort(b,10);for(i=0;i<10;i++)printf("%-4d",b); printf("\n\n");}
页:
[1]