数据结构课程设计—内部排序算法比较

for(i=2; i<=n; i++) { cn[0]++;

if (R[i].key

void Select_Sort(datatype R[ ],int n)//简单选择排序 {

int i,j,k;

for(i=1;i

if (i=k)

{ R[0]=R[k]; R[k]=R[i];

R[i]=R[0]; mn[1]+=3; } } }

void Insert(datatype R[],int n)//直接插入排序****** { int i,j; for(i=2;i<=n;++i) { if(R[i].key

mn[6]+=2; cn[6]++; } cn[6]++;

R[j+1].key=R[0].key; mn[6]++; } else cn[6]++; cn[6]++; } cn[6]++; }

void Bubble_Sort (datatype R[ ], int n)//冒泡排序 {

int i, j; int swap; for(i=1; i

for(j=1; j<=n-i; j++) {

cn[2]++;

if (R[j].key

R[j+1]=R[0]; mn[2]+=3; swap=1; }}

if(swap==0) break; } }

void Zhe_ban(datatype R[ ], int n)//折半插入排序**** { int i,j,low,high,m; for(i=2;i<=n;++i) { R[0].key=R[i].key; mn[7]++; low=1;high=i-1; while(low<=high) {

cn[7]++; m=(low+high)/2; if(R[0].key=high+1;--j) { R[j+1].key=R[j].key; cn[7]++; mn[7]++; } cn[7]++; }

cn[7]++; }

void shell_sorts(datatype R[ ],int n)//希尔排序 { int k,i,j,dk; int dlta[3]={5,3,1}; for(k=0;k<3;++k) { cn[8]++; dk=dlta[k]; mn[8]++; for(i=dk+1;i<=n;++i) { cn[8]++; if(R[i].key0&&(R[0].key

{ R[j+dk].key=R[j].key; cn[8]++; mn[8]++; } cn[8]++; R[j+dk].key=R[0].key; mn[8]++; } } cn[8]++; }cn[8]++; }

void HeapAdjust(datatype R[ ], int s, int t)//堆排序 {

datatype rc; int i,j ; rc=R[s]; i=s;

for(j=2*i; j<=t; j=2*j) { cn[3]++;

if(j R[j].key) break; R[i]=R[j]; mn[3]++; i=j; } R[i]=rc; }

void HeapSort(datatype R[ ], int n)//堆排序*** { int i;

for(i=n/2; i>0; i-- ) HeapAdjust(R, i, n); for(i=n; i>1; i--) { R[0]=R[1]; R[1]=R[i];

R[i]=R[0]; mn[3]+=3; HeapAdjust(R,1, i-1); } }