数据结构实验报告10

宜宾学院实验报告

课程名称 院系 学号 实验日期 数据结构 计算机学院 实验名称 排序 班级 姓名 实验教室 基础五 16级5班 专业 子墨 指导教师 阳万安 软件工程 161105024 2017.10.31 评阅意见 一、实验目的和要求（本次实验所涉及并要求掌握的知识点） 1. 掌握常见的排序算法(插入排序、交换排序、选择排序等)的思想、特点及其适用条件。 2. 能够分析各种算法的效率 3. 熟练掌握常见的排序算法的程序实现。 二、实验内容 1．按照快速排序思想实现快速排序算法 2．在主函数中输入一组数据，测试算法的正确性。 思想：划分，递归 划分：以某个记录为界，将待排序记录分成两部分。一部分记录的关键字小于支点记录的关键字，另一部分记录的关键字大于支点记录的关键字。 实验结果 三、实验环境（本次实验所需要的平台和相关软件） VC++ 6.0 四、实验步骤（针对本次实验计划安排的实验内容写具体实现步骤） 1. 打开VC++ 6.0，新建一个win32控制台工程 2. 添加一个C++资源文件，命名为：exp10.cpp 3. 写入以下代码 /* 1．按照快速排序思想实现快速排序算法 2．在主函数中输入一组数据，测试算法的正确性。 思想：划分，递归 划分：以某个记录为界，将待排序记录分成两部分。一部分记录的关键字小于支点记录的关键字，另一部分记录的关键字大于支点记录的关键字。 */ #include #define MAXSIZE 20 typedef int KeyType; typedef struct{ 第1页共5页

KeyType key; }RedType; typedef struct{ RedType r[MAXSIZE+1]; int length; }SqList; void swap(SqList &L,int low,int high) { L.r[0]=L.r[low]; L.r[low]=L.r[high]; L.r[high]=L.r[0]; } //三个Partition函数任选一个,建议选中间那个，效率更高 //int Partition(SqList &L,int low,int high) //{ // int pivotkey=L.r[low].key; // while(low=pivotkey) // { // --high; // } // swap(L,low,high); // while(low=pivotkey) // { // --high; // } // L.r[low]=L.r[high]; // while(lowpivotkey);//每次找划分右边第一个比轴小的元素，high保存其下标 if(low>=high) break; swap(L,low,high);//交换low，high对应的值 //注意到这个循环里总共只交换了一次，而不是每次找到大的或者小的都会立马交换一次 } swap(L,i,high);//所以在外面应该再交换一次，交换轴和high对应的元素。 return high; } void Qsort(SqList &L,int low,int high) { if(low