南邮数据结构上机实验四内排序算法的实现以及性能比较

1、实验报告(2015/2016学年第二学期)课程名称数据结构a实验名称内部排序算法的实现和性能比较实验时间2016年5月亮26日指导单位计算机科学和技术系指导教师骆健学生姓名聂宇班号b14111615学院(系)经营学院专家信息管理和信息系统实习题名：内排名算法的实现和性能比较b141116名庚宙学号b14111615日2016.05.26一、问题的说明验证教材的各种内排序算法，分析各种排序算法的时间复杂度，改进教材中的快速排序算法，使用随机数发生器生成大数据集合，使子集不到10人的元素师直接插入排序，并执行上述各排序算法系统时钟包含在头文件“time.h”中。二、概要设计文件sort.cpp包含

2、简单选择排序selectsort ()，直接插入排序insertsort ()，双合并气泡排序bubblesort ()，对merge ()进行排序，然后快速排序quicksort () 主函数main的代码如下图所示三、详细设计1 .班级和班级的分层设计这次的程序设计没有对班级进行定义。 程序的主要设计是利用各种内排序算法对随机生成的数列进行排列，除了进行性能比较外，还改进了高速排序。 下图是主函数main的流程图main ()2 .核心算法1 )简单选择排序：简单地选择排名的基本思想是，第一次，在排名对象的记录r1rn中选择最小的记录，将其与r1交换，第二次，在排序的记录r2rn中选择最小

3、的记录，将其第i次是从排名对象的记录rirn中选择最小的记录，将其与ri交换，使顺序序列增长到所有排名结束。2 )直接插入排序插入排序的思想确保在已排序的数组中插入一组无序元素，所插入的数组也已排序。 插入无序组的所有元素后，就完成了规则数组的构建。 阵列n1r是第一个无序阵列(直观地说，这里从1开始阵列，设定为非0 )，n1默认为仅一个元素的秩序阵列，n2插入到仅n1的秩序阵列中时，秩序阵列的元素数为2。 以相似的方式，最初i-1元素已经是有规则的，直到第i元素，在这种情况下，可以仅将第i元素插入规则阵列以维持有规则性。 这将完成整个插入顺序，直到插入最后一个元素为止。3 )泡沫排序：气泡排

4、序在每次遍历数组时，将最大的元素放在数组的末尾。 下一次扫描将排列倒数第二大元素，并按顺序继续，直到最小元素第一次排列，气泡排序完成。4 )快速排序：快速排序虽然采用了分割的想法，但与集成排序不同，先对“工作”(在此为分割或分区)进行递归排序。 高速排序的主要思想是，保证数组的前半部分比后半部分的要素小，然后分别按顺序排序前半部分和后半部分，使所有要素成为顺序。5 )双向整合排序双向耦合排序算法的基本理念是将要重新排序的元素划分成尺寸近似相同的两个子序列，对每一个子序列进行递归耦合排序，直到所述子序列长度变为1，最后，使用所述组合算法来对重新排序的两个子序列进行一个排序双键排序算法的核心部分是

5、将子问题的解结合到原始问题上的操作。 典型的操作是创建一个大小与要合并的两个子序列的总长度相同的新序列。 比较两个子序列的最小值，将其中较小的一个输出到新序列，并重复此过程，直到其中一个子序列为空。 如果其他子序列中还有未输出的元素，则将剩馀的元素依次输出到新序列中。 最终得到有秩序的序列。另外，快速排序得到了改进，算法流程图改进如下gquicksort ()四、程序代码模板，模板，模板void gquicksort(t a，int n) /改进的快速排序举止gqsort(a，0，n-1 )以下模板，模板，模板void gqsort(t a，int left，int right )举止ps、p

6、s；ps (s=9)举止ps (ps )；ps#include#include模板，模板，模板语音交换(ta，t b )举止t temp=a；a=b；b=临时；以下模板，模板，模板void选择(ta ，int n) /简单选择排序举止int small；for(int i=0； void insertsort(t a，int n) /直接插入排序举止for(int i=1； 第十届冬奥会void bubblesort(t a，int n) /泡沫排序举止ps、ps、ps；i=n-1；while(i0)举止最后=0；for(j=0； 日本航空快速排序(ta ，int n) /快速排序举止qsor

7、t(a，0，n-1 )以下模板，模板，模板void qsort(t a，int left，int right )举止ps、ps；ps (ps )；psvoid gquicksort(t a，int n) /改进的快速排序举止ps ps (a，0，n-1 )以下模板，模板，模板void gqsort(t a，int left，int right )举止ps、ps；ps (k=9)举止ps (ps )；psvoid merge(t a，int i1，int j1，int i2，int j2) /双向合并排序举止t* temp=new tj2-i1 1；int i=i1，j=i2，k=0；while(i=j1j=j2)举止ps (ps=ps )tempk =ai ；else tempk =aj ；以下while (i=j1)tempk =ai ；while(j=j2)tempk =aj ；for(i=0； void mergesort(t a，int n )举止int i1、j1、i2、j2；int size=1；while(sizen-1 )j2=n-1；elsej2=i2 size-1；merge(a，i1，j1，i2，j2)i1=j2 1；以下size*=2；以下以下int main ()举止时钟_ t开始，完成；srand (时间(空) )