数据结构排序算法的分析和比较(包涵源代码)

} free(pvector); }

voidQuickSort(SortObject *pvector,intleft,intright,unsigned long*compare,unsigned *exchange) { inti,j;

RecordNode temp; if(left>=right) return; i=left; j=right; temp=pvector->record[i]; (*exchange)++; while(i!=j) { while((pvector->record[j].key>=temp.key)&&(j>i)) { (*compare)++; j--; } if(irecord[i++]=pvector->record[j]; (*exchange)++; } while((pvector->record[i].key<=temp.key)&&(j>i)) { (*compare)++; i++; } if(irecord[j--]=pvector->record[i]; (*exchange)++; } } pvector->record[i]=temp; (*exchange)++;

QuickSort(pvector,left,i-1,compare,exchange); QuickSort(pvector,i+1,right,compare,exchange); }

voidSortMethod(void) { inti,j;

unsigned long num[3][12]={0}; SortObject *pvector=(SortObject *)malloc(sizeof(SortObject)); int random;

long

randomize(); for(j=0;j<3;j++) { for(i=0;irecord[i].key=random(5000); pvector->n=MAXSORTNUM[j]; InsertSort(pvector,&num[j][0],&num[j][1]); SelectSort(pvector,&num[j][2],&num[j][3]); BubbleSort(pvector,&num[j][4],&num[j][5]); ShellSort(pvector,4,&num[j][6],&num[j][7]); Heapsort(pvector,&num[j][8],&num[j][9]);

QuickSort(pvector,0,MAXSORTNUM[j]-1,&num[j][10],&num[j][11]); } printf(\ for(j=0;j<3;j++) {

printf(\

printf(\ Exchanged-->%-7ld\\n\printf(\ Exchanged-->%-7ld\\n\printf(\printf(\ Exchanged-->%-7ld\\n\printf(\ Exchanged-->%-7ld\\n\printf(\ Exchanged-->%-7ld\\n\ if(j!=2) printf(\ getchar(); } } void main() { SortMethod(); }

六、程序运行与测试

图6.1 数据长度为20时算法运行界面

图6.2 数据长度为100时的运行界面

图6.3 数据长度为500时的运行界面

通过不同数据长度排序比较我们可以清楚地知道，当数据规模不断增加时，各种排序算法之间的差别是很大的。其中在这六种不同的算法中，快速排序的比较和交换次数是最少的，也就是说它是其中最快的一种排序算法，其他几种算法都有有些差异，其中冒泡排序最慢。

七、心得体会

通过此次的课程设计使我更加深入的了解了各种排序算法的思想，基本原理。增强了实际动手能力，更好的把理论和实践相结合，充分理解了各种排序算法的优缺点，并在课程设计的整个过程中和同学积极沟通，在学习过程中增加了与同学之间理解和认同，更好的相互学习相互帮助。本实验采用随机函数生成各种排序算法调用的相关数据长度的数据，利用randomize()初始化随机数种子，最后利用一个for循环把运行比较得到的结果输出。在此区间我就不懂的东西请教了很多同学，使自己认识到了自己的不足，还有很多地方有待提高和改正，不管怎样通过此次的课程设计我受益匪浅。

八、参考文献

【1】秦锋、袁志祥.数据结构（C语言版）例题详解与课程设计指导.北京：清华大学出版社 【2】百度文库 www. Wenku.baidu,com

【3】耿国华.数据结构（用C语言描述） . 北京：高等教育出版社，2011.6