数据结构实验4 排序

1实验4快速排序一、实验目的和要求1在掌握各种排序方法的排序过程的基础上，完成快速排序算法程序设计。2能够对排序算法进行基本的复杂度分析。二、实验内容排序就是把一组元素按照某个域的值的递增或递减的次序重新排列的过程。快速排序在待排序记录序列中任取一个记录作为枢轴，以它作为比较的“基准”，将待排序划分为左右两个子序列，使行左边子序列中记录的关键字均小于等于枢轴，右边子序列中各记录的关键字都大于等于枢轴。对所划分的两组分别重复上述过程，直到各个序列的记录个数为1时为止。快速排序函数原型QuickSort(SeqListsq)。设计一个算法，在顺序表存储结构上实现快速排序。排序数据为学生的考试成绩单。成绩单由学生的学号、姓名和成绩组成，设计一个程序对给定的n个学生的成绩单按照名次列打印出每个学生的名次、学号、姓名和成绩。三、实验步骤1．输入待排序的记录2.对自定义记录类型重载比较运算符3．排序1）并选择第一个记录作为pivotkey记录2）从high指向的记录开始,向前找到第一个关键字的值小于Pivotkey的记录,将其放到low指向的位置,low+13）.从low指向的记录开始,向后找到第一个关键字的值大于Pivotkey的记录,将其放到high指向的位置,high-14）重复2),3)，直到low=high，将枢轴记录放在low(high)指向的位置5）重复2),3),4)，直到整个记录有序为止6)输出排序记录，完成比较。4.附加要求：不采用运算法重载的方式，而是定义compare函数指针，通过传给quicksort函数指针，完成排序。2四、实验提示算法实现：#includeiostream.h#defineMaxSize100typedefintDataType;classCRecord{public:intNo;stringname;intgrade;}TypdefCRecordDataType;classSeqList{public:CRecord*data;intlength;}//创建顺序表VoidSLCreat(SeqList&sq);{CRecordx;length=0;cout请输入数据元素数”;cinsq.length;sq.data=newCRecord[sq.length];cout请输入数据元素值:no,,namegrade;for(inti=0;in;i++){cinsq.data[i].nosq.data[i].namesq.data[i]grade;}}//排序VoidSort(SeqList&sq){SLCreat(sq);QuickSort(sq,0,sq.length);}//快速排序voidQuickSort(SeqList&sq,intlow,inthigh)3{intpos;if(lowhigh){pos=partition(sq,low,high);QuickSort(sq,low,pos-1);QuickSort(sq,pos+1,high);}}intpartition(SeqList&list,inti,intj){DataTypepivotkey;pivotkey=list[i];while(ij){while(ij&&list[j]=pivotkey)--j;if(ij)list[i++]=list[j];while(ij&&list[i]=pivotkey)++i;if(ij)list[j--]=list[i];}list[i]=pivotkeylreturni;}//将顺序表显示在屏幕上voidSLPrint(SeqList&sq){cout快速排序结果:’for(inti=0;ilist.length;i++)coutisq.data[i].nosq.data[i].namesq.data[i].gradeendl;coutendl;}voidmain(){SeqListmyList;SLCreat(SeqList&mylist);Sort(mylist);SLPrint();}