各类排序算法.docx

1、各类排序算法/*/各类排序算法/*#include #include #include typedef struct int key; /主关键字NODE;/*/随机数组,作为全局数据/*NODE DATA100;/*/创建磁盘文件f:resource.dat/保存100个100以内的随机数(无重复)/*void creatfile() FILE *fp; int i,j,key,flag; int data100=0; unsigned seed; if(fp=fopen(f:resource.dat,wb+)=NULL) printf(打开文件失败!n); exit(0); seed=ti

2、me(NULL); srand(seed); /设置随机种子 for(i=0;i=99;) key=rand()%1000; flag=1; for(j=0;j=i-1;j+) if(key=dataj) flag=0; break; if(flag) datai+=key; for(i=0;i=99;i+) putw(datai,fp); /写一个整数到磁盘文件 fclose(fp);/*/导入磁盘文件f:resource.dat中的信息/将文件中的数据，存入全局数组中/*void load() FILE *fp; int i; if(fp=fopen(f:resource.dat,rb+)

3、=NULL) printf(打开文件失败!n); exit(0); for(i=0;i=99;i+) DATAi.key=getw(fp); fclose(fp);/*/输出随机数组/*void prn(NODE data) printf(n); for(int i=0;i=99;i+) printf(%3d ,datai.key); if(i+1)%5=0) printf(n); /*/快速排序的区域划分算法/在区间了low和high之间进行一次划分/*int partition(NODE data,int low,int high) int i=low; int j=high; int t

4、=datai.key; /t为划分的基准值 /寻找基准点的位置 do while(t=dataj.key&ij)/基准点与右半区的元素逐个比较大小 j-; / if(ij) /右半区中找到一个比基准点小的记录 datai=dataj; /将基准点与该记录交换,将小的记录放到左半区中 i+; while(datai.key=t&ij) /在基准点的左半区中搜索比它大的记录 i+; if(ij) /左半区中找到一个比基准点大的记录 dataj=datai; /将基准点与该记录交换,将大的记录放到右半区中 j-; while(ij); /如此重复,直到左右半区相接 datai.key=t; retu

5、rn i;/*/快速排序算法/*void quicksort(NODE data,int low,int high) int position; if(lowhigh) /当区间下界小于区间上届d position=partition(data,low,high); /将该区间分成两半,position为分界点 quicksort(data,low,position-1); /对左半区进行快速排序 quicksort(data,position+1,high); /对右半区快速排序 /*/选择排序/*void selesort(NODE DATA) int i,j; NODE t; for(i

6、=0;i99;i+) /n个数,排序n-1轮 for(j=i+1;jDATAj.key) /发现更小的数,则交换 t=DATAi; DATAi=DATAj; DATAj=t; /本循环结束,DATAi中是本轮找到的最小值 /*/直接选择排序/*void dselesort(NODE DATA) int i,j,k; NODE t; for(i=0;i99;i+) k=i; for(j=i+1;jDATAj.key) /记下最小值的位置 k=j; /把DATAi和最小值DATAk交换 if(k!=i) t=DATAi;DATAi=DATAk;DATAk=t; /*/冒泡排序/*void paso

7、rt(NODE DATA) int i,j; NODE t; for(i=0;i99;i+) for(j=0;jDATAj+1.key) t=DATAj,DATAj=DATAj+1,DATAj+1=t; /*/改进的冒泡排序/*void dpasort(NODE DATA) int i=0,j; NODE t; int flag; do flag=1; for(j=0;jDATAj+1.key) t=DATAj,DATAj=DATAj+1,DATAj+1=t; flag=0; i+; /比较的轮次增1 while(!flag);/*/筛选法,将:以结点i为根的二叉树,调整成一个大根堆/调整范围

8、: 结点i-结点j/*void sift(NODE data,int i,int j) NODE temp; int p=2*i; /p指向i的左孩子 int t; while(p=j) /如果i的左孩子存在,则调整,否则,i是叶子,不调整 t=p; /t指向i的左孩子 if(pj) /如果i有右孩子 if(datap.keydatap+1.key) t=p+1; /p指向键值较大的孩子 if(datai.key=1;k-) sift(data,k,n); /对非叶子结点k,利用调整算法 /使以该节点k为根的树变成大根堆 /调整区间:(k-n)/*/堆排序算法/数据集合1-n之间的数进行堆排序

9、/数据元素data0留空/可作为辅助变量,实现两个元素的互换/*void heapsort(NODE data,int n) int i; creatheap(data,n); /将data中的n个元素创建成大根堆 for(i=n;i1;i-) /堆排序,data1中始终为无序区的最大值 data0=datai; /将根(最大值)换到无序区的末尾 datai=data1; /data0作为辅助变量 data1=data0; sift(data,1,i-1); /调整无序区中的数据,使之保持大根堆性质 /*/归并/*void merge(NODE data,int low,int m,int h

10、igh) int i=low,j=m+1,p=1; NODE t101; /辅助存储空间,可采用动态申请的方式 / t=(NODE *)malloc(sizeof(NODE)*(high-low+1) /动态申请辅助存储空间 while(i=m&j=high) /合并 tp+=datai.keydataj.key?datai+:dataj+; while(i=m)/若前一组还有多余数据,全部复制到辅助空间 tp+=datai+; while(j=high) /若后一组还有多余数据,全部复制到辅助空间 tp+=dataj+; for(p=1,i=low;i=high;i+,p+) datai=t

11、p; /从辅助空间写回到原数据空间/*/一个轮次的归并算法/*void mergepass(NODE data,int n,int length) int i; for(i=1;i+2*length-1=n;i+=2*length) /在data的某个区间上进行归并排序 /区间下界:i,上界:i+2*length-1 /上下界分界点: i+length-1 merge(data,i,i+length-1,i+2*length-1); if(i+length-1n) merge(data,i,i+length-1,n);/*/自底向上的二路归并排序算法/*void mergesort(NODE

12、data,int n) int length; for(length=1;lengthn;length*=2) /进行若干轮次的归并排序, /n个数,归并log2n次,分组元素个数为1,2,4,8,16.2length mergepass(data,n,length); /*/直接插入排序（不带监视哨）/*void inser() int i,j; NODE t; for(i=0;i0;j-) /寻找插入点，并进行元素的移动 if(t.keyDATAj-1.key) /如果前一结点的键值比待插入点大 DATAj=DATAj-1; /结点向后移动 else break; /否则，找到插入点 DA

13、TAj=t; /插入待排序的结点 /*/直接插入排序（带监视哨）/*void sinser(NODE data) int i,j; for(i=2;i=100;i+) j=i; data0=dataj; /设置监视哨，将其设置为待插入的结点 while(data0.key=1) /依次取出各增量 for(k=n;k=0&t.keyDATAj.key) /比较两个记录的大小 DATAj+n=DATAj; /插入排序，较大的前一记录向后移动 j-=n; /寻找本分组的前一记录 DATAj+n=t; /插入一个记录 n/=2; /增量减半 /*/主函数/*void main() int i; cre

14、atfile();/创建磁盘文件 load(); /导入磁盘文件信息 prn(DATA);/ quicksort(DATA,0,99); /在区间0-99之间进行快速排序/ selesort(DATA); /选择排序/ dselesort(DATA); /改进的选择排序 pasort(DATA); /冒泡排序/ dpasort(DATA); /改进的冒泡排序 / NODE data101;/ for(i=1;i=100;i+)/ datai=DATAi-1; /为方便描述,将原始数据DATA导入到data101中 /data0留空/ inser(); shellsort();/ sinser(data);/ prn(data);/ creatheap(data,100);/ prn(data);/ heapsort(data,100); /对data中的100个数进行堆排序,排序区间(1-100)/ mergesort(data,100); /对data中的100个数进行归并排序,排序区间(1-100)/ for(i=1;i=100;i+)/ DATAi-1=datai; prn(DATA); / mergesort(data);