2022年排序算法c语言 .pdf

《2022年排序算法c语言 .pdf》由会员分享，可在线阅读，更多相关《2022年排序算法c语言 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include#define MAX 5000 int RMAX;float compare;/*记录比较次数的全局变量*/float sort;/*记录排序次数的全局变量*/*插入排序*/void Insertsort(int r,int n)int i,j,temp,curr,index;for(i=1;in;i+)temp=ri;/*记录当前值*/curr=index=i;for(j=0;ji;j+)compare+;if(rirj)index=j;/*记录插入位置*/break;while(indexcurr)/*将插入位置到当前位置之间的数后移*/sort+;rcurr=rcurr

2、-1;curr-;rindex=temp;/*当前值到指定位置*/*选择排序*/void SelectSort(int r,int n)int i,j,min,temp;for(i=0;in;i+)for(j=i+1;jrj)/*如果当前元素rj 比索引指向的元素ri 小，换位*/名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -sort+;temp=ri;ri=rj;rj=temp;/*希尔排序*/*以 2 的 n 次方为步长*/void ShellSort(int r,int n)int gap,i,j,temp;for(gap=n/2;gap0;gap/=2)/*以

3、 2 的 n 次方为步长*/for(i=gap;i=0)&(rj rj+gap);j-=gap)temp=rj;rj=rj+gap;rj+gap=temp;sort+;compare+;/*以上课给定数为步长*/void ShellSort2(int r,int n)int gaps=1,5,13,43,113;int i,j,k,gap,temp;for(k=0;gapsk=0)/*每次步长变小*/gap=gapsk;for(i=gap;i=gap&rj-gaptemp)/*当前元素以gap 为步长找位置*/compare+;rj=rj-gap;j=j-gap;rj=temp;/*将当前元素

4、放到他的位置*/sort+;/*归并排序*/void MergeSort(int array,int top,int bottom)if(topbottom)int middle=(top+bottom)/2;/*找到中间位置*/sort+;MergeSort(array,top,middle);/*中间前递归，直到剩一个数*/MergeSort(array,middle+1,bottom);/*中间后递归，直到剩一个数*/merge(array,top,middle,bottom);/*排序，合并*/int merge(int array,int top,int middle,int bot

5、tom)int i,j;int tempMAX;int left=top;int right=middle+1;int tempindex=0;int begin=0;int end=0;while(left=middle&right=bottom)compare+;if(arrayleft=arrayright)temptempindex=arrayleft;left+;else 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -temptempindex=arrayright;right+;tempindex+;compare+;if(left=middle)begi

6、n=left;end=middle;else begin=right;end=bottom;for(i=begin;i=end;i+)sort+;temptempindex=arrayi;tempindex+;for(i=top,j=0;i=bottom;i+,j+)sort+;arrayi=tempj;/*快速排序*/void QuickSort(int r,int low,int high)int i,j,temp;i=low;j=high;temp=rlow;while(ij)/*将比 temp 大的放到后面，小的放到前面*/while(ij)&(temprj)/*从后往前找比temp

7、小的位置j*/j-;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -compare+;if(ij)ri=rj;/*将小的数放到前面*/i+;sort+;while(iri)/*i后，j 之前的比temp 大 ri 的位置*/i+;compare+;if(ij)sort+;rj=ri;/*将比 temp 大的放入后面*/j-;ri=temp;/*将 temp 放入数组*/if(lowi)/*若最小位置比i 小，执行前半部分排序*/QuickSort(r,low,i-1);if(jhigh)/*若最大位置比j 大，执行后半部分排序*/QuickSort(r,j+1,high

8、);void Heapify(int s,int m)int j,temp;temp=Rs;j=2*s;while(jRj+1&jm)j+;if(temp0;i-)Heapify(i,n);compare+;void Heap_sort(int n)int i;BulidHeap(n);for(i=n;i1;i-)sort+;R0=R1;R1=Ri;Ri=R0;Heapify(1,i-1);void main()int r1MAX,r2MAX,r3MAX,r4MAX,r5MAX,n=MAX,i,j;int sum;printf(compare sort sumn);printf(-n);for

9、(i=0;i4;i+)for(j=0;jn;j+)r1j=r2j=r3j=r4j=r5j=RMAX=rand()%100;for(j=0;j4;j+)if(j=i)printf(%d,j+1);名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -compare=0;sort=0;Insertsort(r1,n);printf(InsertSort%10.0f%10.0f%10.0f n,compare,sort,compare+sort);compare=0;sort=0;SelectSort(r2,n);printf(SelectSort%10.0f%10.0f%10.0

10、f n,compare,sort,compare+sort);compare=0;sort=0;ShellSort(r3,n);printf(ShellSort%10.0f%10.0f%10.0f n,compare,sort,compare+sort);compare=0;sort=0;MergeSort(r4,0,n);printf(MergeSort%10.0f%10.0f%10.0f n,compare,sort,compare+sort);compare=0;sort=0;QuickSort(r5,0,n-1);printf(QuickSort%10.0f%10.0f%10.0f n,compare,sort,compare+sort);compare=0;sort=0;Heap_sort(n);printf(HeapSort%10.0f%10.0f%10.0f,compare,sort,compare+sort);if(i!=3)printf(n);getch();名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -