几种常见的排序算法的实现与性能分析数据结构课程设计报告

附录（源程序清单）

#include #include #include #include #define L 100 #define FALSE 0 #define TRUE 1 /*typedef struct { int key;

char otherinfo;

}RecType;*/

//typedef RecType Seqlist[L+1]; int s[100],R[100]; int num;

int times=0,changes=0; //Seqlist R; void Insertsort(); void Bubblesort();

void QuickSort(int low,int high); void Shellsort(); void Selectsort(); void Heap(); int Partition(); void main() { //Seqlist S; int i,k;

char ch1,ch2,q;

32

printf(\产生100个随机数：\\n\

srand((unsigned)time(NULL)); for(i=1;i<=L;i++) {

s[i]=rand()0; }

for(i=1;i<=L;i++) {

printf(\ }

printf(\排序数据已经输入完毕！\ for(i=1;i<=L;i++)

R[i]=s[i];

ch1='y';

while (ch1=='y'||ch1=='Y') {

printf(\排 序 性 能 分 析\\n\

printf(\ 1--------直接插入排序 ---------*\\n\ printf(\ 2--------希 尔 排 序 ---------*\\n\

printf(\

printf(\ 3--------冒 泡 排 序 ---------*\\n\ printf(\ 4--------快 速 排 序----------*\\n\ printf(\ 5--------选 择 排 序 ---------*\\n\ printf(\ 6--------堆 排 序----------*\\n\ printf(\ 0--------返 回----------*\\n\

printf(\ printf(\请选择菜单号（0---6）:\

scanf(\for(i=1;i<=L;i++)

R[i]=s[i]; switch(ch2)

33

}

}

{

case '1':Insertsort();break; case '2':Shellsort();break; case '3':Bubblesort();break;

printf(\尚未排序的数据为（回车继续）：\ for(k=1;k<=L;k++)

printf(\ num=0;QuickSort(1,L); break;

getchar();printf(\

case '4':

case '5':Selectsort();break; case '0':ch1='n';break;

default:printf(\输入错误！请重新输入！\\n\\t\\t\

case '6':Heap();break;

if(ch2!='0') {

if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8') } }

printf(\排序演示输出完毕！\\n\q=getchar(); if (q!='\\xA') {

getchar();ch1='n'; }

printf(\请按回车键返回主菜单...\

void Insertsort()//直接插入排序 {

34

int i,j,k,m=0; for(k=1;k<=L;k++)

printf(\getchar(); printf(\for(i=2;i<=L;i++) {

if(R[i]

R[0]=R[i];j=i-1; while(R[0]

printf(\尚未排序的数据为（回车继续）：\

times++; changes++; }

printf(\for(i=1;i<=L;i++)

printf(\printf(\ }

m++; times++; R[j+1]=R[j];j--; }

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

changes++;

printf(\最终排序结果为：\

printf(\直接插入排序的比较次数为%d\ printf(\直接插入排序的移动次数为%d\ times=0; changes=0;

35