实验五实验五 快速排序快速排序【实验时间实验时间】 【实验地点实验地点】 【实验目的和要求实验目的和要求】1理解排序稳定性含义，掌握各种排序算法的稳定性；2掌握各种内部排序的基本算法和特点；3掌握快速排序的排序过程，程序实现快速排序。【实验类型实验类型】 验证性【实验时数实验时数】 2 学时【实验设备实验设备】 计算机【参考资料参考资料】 1数据结构题解2C 程序设计【实验内容实验内容】掌握快速排序的算法程序实现排序过程。具体算法可描述如下：设初始序列为 a1,a2,an，以序列中的某个元素 ai 为基准(轴)，经调整后，使得 ai左边的元素均小于 ai，右边的均大于等于 ai，而后对这两个子区再分别使用快速排序。具体要求(1) 需要用一维数组 a 来存储等待排序的序列；(2) 设置两个工作指针 i 和 j；(3) 每次快速排序都以排序区域的首元素为基准(轴)；(4) 程序用递归函数来实现。【实验分析实验分析】基本思想：在待排序的 n 个记录中任取一个记录（通常取第一个记录） ，把该记录放入最终位置后，整个数据区间被此记录分割成两个区间。所有关键字比该记录关键字小的放置在前子区间，所有关键字比它大的放后子区间中，并把该记录排在这两个子区间的中间，这样就完成了一趟快速排序。然后分别对两个子区间重复上述过程，直至划分的子区间长度为 1。一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。具体做法是：设两个指示器 I 和 j，它们的初值分别为指向无序区第一个和最后一个记录。假设无序区中记录为 R1.n，则 I 的初值为 R1，j 的初值为 Rn，首先将 R1移到tmp 中作为基准，令 j 自 n 起向左扫描直至 Rj.keytmp.key，将 Ri移至 j 所指的位置上，一次重复直至 Ij，此时所有 Rk（k=1,2,j-1）的关键字都小于 tmp.key 而所有 Rk（k=j+1,j+2,n）的关键字都大于 tmp.key，则可将 tmp 中的记录移至 I 所指位置 Ri，它将无序中记录分割成 R1.j-1和 Rj+1.n，然后再分别进行排序。Void QuickSort(SqList R,int s,int t) int I=s,j=t;SqList tmp;If(sIif(IIIf(Ij) Rj= Ri;j- -;Ri=tmp;QuickSort(R,s,I-1);QuickSort(R,i+1,t);【注意事项注意事项】1.学生上机时要严格遵守实验规章制度，若实验设备出现故障，应及时向实验指导教师反映，不要私自拆卸实验设备。2.独立完成实验要求的内容，仔细观察和记录实验结果，领会实验目的，并认真完成实验 报告。