2022年排序算法c语言 2.pdf
#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-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) /* 以 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;/* 将当前元素放到他的位置*/ 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 bottom) 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) begin=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 小的位置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); 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(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.0f 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 页 - - - - - - - - -
