各种排序算法比较

各种排序算法的比较程序

#include #include #include

#define MAXSIZE 30000 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b))

typedef struct { int k; int n; }Node;

typedef struct { Node r[MAXSIZE+1]; int l; }SqList; SqList L;

Node TR1[MAXSIZE+1]; Node TR2[MAXSIZE+1]; int aa[MAXSIZE];

void printGUI() { printf(\**\\n\ printf(\**\\n\ printf(\排序算法比较程序******************************\\n\ printf(\**\\n\ printf(\**\\n\}

void init() {

int t; L.l=0; int i; for(i = 0; i < MAXSIZE; i++) { t = rand() % 65535; aa[i] = t; L.r[i].k = t; L.l = i; } printGUI(); }

void rollback() { int i; for(i=0;i

L.r[i].k = aa[i]; } }

void insertSort() { clock_t start, finish; double insertSorttime = 0.0; start = clock(); int i,j; for(i=2;i<=L.l;++i) { if(LT(L.r[i].k,L.r[i-1].k)) { L.r[0].k=L.r[i].k; L.r[0].n=L.r[i].n; for(j=i-1;j>0&<(L.r[0].k,L.r[j].k);j-=1) {L.r[j+1].k=L.r[j].k; L.r[j+1].n=L.r[j].n; }//记录后移，查找插入位置 L.r[j+1].k=L.r[0].k;//插入 L.r[j+1].n=L.r[0].n;

} }

finish = clock();

insertSorttime = (double)(finish - start) / CLOCKS_PER_SEC;

printf(\ /*用户进程所耗费的时间*/ rollback(); }

//Shell排序，统计数据排序所用时间 void ShellInsert(int dk) {

//对顺序表L做一趟希尔插入排序，和直接插入排序相比，做了以下改动 //1、前后记录的增量是dk，而不是1 //2、r[0]只是暂存单元，不是哨兵。当j<=0时，找到了插入位置 int i,j; for(i=dk+1;i<=L.l;++i) { if(LT(L.r[i].k,L.r[i-dk].k)) { L.r[0].k=L.r[i].k; L.r[0].n=L.r[i].n; for(j=i-dk;j>0&<(L.r[0].k,L.r[j].k);j-=dk) {L.r[j+dk].k=L.r[j].k; L.r[j+dk].n=L.r[j].n; }//记录后移，查找插入位置 L.r[j+dk].k=L.r[0].k;//插入 L.r[j+dk].n=L.r[0].n; } }

}//ShellInsert

void ShellSort() { clock_t start, finish; double ShellSorttime = 0.0; start = clock(); //对顺序表做希尔插入排序 int dlta[5]={121,40,13,4,1};

int t=5,k=0; for(k=0;k

finish = clock();

ShellSorttime = (double)(finish - start) / CLOCKS_PER_SEC;

printf (\ /*用户进程所耗费的时间*/ rollback();

}//ShellSort

void SelectSort() { int i,j; int temp; int max = 0; clock_t start, finish; double selectSorttime = 0.0; start = clock(); for(i=0;i

printf (\ /*用户进程所耗费的时间*/