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

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。

#include<stdio.h> #include<stdlib.h> #include<math.h>

#define MAXNUM 100 #define RADIX 10 #define MAX 8

#define MAX_SPACE 10000 typedef int KeysType; typedef struct {

KeysType keys[MAX];

int next; }SLCell; typedef struct {

SLCell r[MAX_SPACE]; int keynum; int recnum; }SLList;

typedef int ArrType[RADIX];

typedef struct { int key;

} datatype;

datatype R[MAXNUM];//定义结构体数组

int cn[11]={0}; int mn[11]={0};

void CreateSLList(SLList &L,int n,datatype R[ ]) //基数排序 {

L.recnum=n; L.keynum=3;

mn[10]+=2;

//printf("please input data numbers:/n"); //scanf("%d",&L.recnum);

//printf("please input keynumbers:/n"); //scanf("%d",&L.keynum);

//printf("please input %d numbers:/n",L.recnum); for(int i=1;i<=L.recnum;i++) { cn[10]++;

int j=L.keynum-1;

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。

L.r[i].keys[j--]=R[i].key/100;

L.r[i].keys[j--]=R[i].key%100/10; L.r[i].keys[j]=R[i].key%10; mn[10]+=3; }

for(i=0;i<L.recnum;++i) {

L.r[i].next=i+1;

}

cn[10]++; mn[10]++;

L.r[L.recnum].next=0; mn[10]++; }

void Display(SLList L) //基数排序 { L.keynum=3;

mn[10]++;

for(int i=L.r[0].next;i;i=L.r[i].next) {

cn[10]++;

for(int j=L.keynum-1;j>=0;j--) { printf("%d",L.r[i].keys[j]); cn[10]++; } cn[10]++; printf(" "); } cn[10]++; printf("\n"); }

void Distribute(SLCell (&r)[MAX_SPACE],int i,ArrType &f,ArrType &e) //基数排序 {

int j,p;

for(j=0;j<RADIX;j++) {

cn[10]++; f[j]=0; mn[10]++;

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。

}

cn[10]++;

for(p=r[0].next;p;p=r[p].next) { cn[10]++; j=r[p].keys[i];

mn[10]++;

if (!f[j]) { f[j]=p; mn[10]++; } else {

r[e[j]].next=p; mn[10]++;

}

e[j]=p; mn[10]++; }

cn[10]++;

}

void Collect(SLCell (&r)[MAX_SPACE],int i,ArrType f,ArrType e) //基数排序 {

int j,t;

for(j=0;!f[j];j++); { cn[10]++; r[0].next=f[j];

}

mn[10]++;

cn[10]++; t=e[j];

mn[10]++;

while (j<RADIX-1) {

cn[10]++;

for(j++;j<RADIX-1&&!f[j];j++);

{

cn[10]++;

if (f[j]) {

r[t].next=f[j];

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。

t=e[j];

mn[10]+=2; } }

cn[10]++;

}

cn[10]++; r[t].next=0; mn[10]++; }

void RadixSort(SLList &L) //基数排序 {

int i;

L.keynum=3; mn[10]++;

ArrType f,e;

for(i=0;i<L.keynum;i++) {

cn[10]++;

Distribute(L.r,i,f,e);

Collect(L.r,i,f,e);

//printf("第%d趟收集后:\n",i+1); //Display(L); printf("\n"); } cn[10]++;

}

void A(datatype R[ ], int n)//基数排序**** {

SLList L;

CreateSLList(L, n,R);

//printf("排序前的结果是:\n"); //Display(L);

RadixSort(L);

//printf("排序后的结果是:\n"); //Display(L); }

void D_InsertSort(datatype R[ ], int n)//直接排序 {

int i,j;

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。

for(i=2; i<=n; i++)

{ cn[0]++;

if (R[i].key<R[i-1].key) {R[0]=R[i]; mn[0]++; for(j=i-1; R[0].key<R[j].key; j--)

R[j+1]=R[j];

R[j+1]=R[0]; mn[0]+=2;

} } }

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

int i,j,k;

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

{

cn[1]++;

if(R[j].key<R[k].key) k=j; }

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<R[i-1].key)

{

cn[6]++;

R[0].key=R[i].key; R[i].key=R[i-1].key; mn[6]+=2;

for(j=i-2;R[0].key<R[j].key;--j) { R[j+1].key=R[j].key;

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。

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)//冒泡排序 …… 此处隐藏：7733字，全部文档内容请下载后查看。喜欢就下载吧 ……