文档介绍：山西大学计算机与信息技术学院实验报告姓名学号 2009241032 专业班级2009级计算机科学与技术课程名称数据结构实验实验日期2011年9月5FI实验名称排序算法的比较成 :编写程序,实现插入排序、选择排序及快速排序这三种内部排序算法,并进行比较,用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。分析比较结果,得出选择这三种排序算法的一般原则。,基本操作是将一个记录插入到己排好序的有序表中,从而得到一个新的记录数增1的有序表。选择排序的基本思想是,每一趟在n-i+l(i=l,2......n-l)个记录中选取关键字最小的记录作为有序序列屮第i个记录。一趟快速排序的做法是,附设两个指针low和high,初值分别为low和high,枢轴记录的关键字为pivotkey,先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换,然后从low所指位置起向后搜索,找到第一个关键字大于pivotkey的记录和枢轴记录互相交换,重复这两步直到low二high。三•实验环境使用MicrosoftVisualC++。四•主要算法#include<>#include<>#defineMAXSIZE20typedefintKeyType;typedefintInfoType;typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项}RedType;〃记录类型typedefstruct{RedType*r[MAXSIZE+l];//r[0]闲置或用作哨兵单元intlength;//顺序表的长度}SqList;//顺序表类型〃构造顺序表SqListCreatSqList(SqList&L){coutvv”请输入顺序表的长度:”;cin»L」ength;inta,i;RedType*s;cout«"请输入一组待排序列构成顺序表:”;for(i=l;i<=L」ength;i++){s二newRedType;cin»a;s->key=a;[i]=s;}returnL;}〃输出顺序表voidShowSqList(SqList&L){inti;for(i=l;i<=L」ength;i++)cout«[i]->key«"}〃插入排序voidlnsertSort(SqListL){for(inti=2;i<=L」ength;++i)if([i]->key<[i-l]->key){[O]=[i];[i]=[i-l];for(intj=i-2;[0]->key<[j]->key;-j)[j+l]=[j];[j+l]=[O];}cout«endl«"插入排序后:";ShowSqList(L);}〃快速排序intPartition(SqList&L,intlowjnthigh){KeyTypepivotkey;[0]=[low];pivotkey=[low]->key;while(low<high){while(low<high&&[high]->key