北邮数据结构实验报告-排序

1、北京邮电大学数据结构测试报告实验名称：实验4的排序学生姓名：班级级别：班级编号：号码：日期：2014年1月4日实验的目的学习、实现和比较各种排序算法，掌握各种排序算法的优缺点，以及各种算法的使用。2实验内容2.1主题1使用简单数组来实现以下排序算法并进行比较。排序算法：1.插入排序2.希尔排名3、气泡排序4.快速排序5、简单选择排序6.堆排序(可选)7、合并排序(可选)8.基数排序(可选)9.其他的要求：1.测试数据分为三类：正序、负序和随机数据2.对于这三种类型的数据，比较上述排序算法中关键字的比较时间和移动时间(其中关键字交换计为3次移动)。3.对于这三种类型的数据，将上述排序算法中不同算

2、法的执行时间与微秒(可选)进行比较4.分析2和3的结果，验证上述算法的时间复杂度编写并测试main()函数，以测试线性表的正确性。3程序分析3.1存储结构顺序存储结构阵列3.2关键算法分析1.插入排序：将要排序的序列中的每条记录插入到之前排序的序列中，直到所有记录都被排序完毕Void insertsort (intr ，intn，int * compare，int * move)/insert sort* compare=0；* move=0；int I；int j；对于(I=1；I=0；j -)(*比较)；(*移动)；rj 1=rj；如果(j=0)(*比较)；rj 1=x；2.希尔排序：首先

3、，将整个序列分成几个子列，并对每个子列应用直接插入排序。当整个序列基本有序时，直接插入排序再次应用于所有记录空隙壳插入(intr ，intn，int * compare，int * move)/希尔排序* compare=0；* move=0；int j；对于(int d=n/2；d=1；/间距越来越小对于(int I=d；I=n-1；/决定是否从d开始逐个元素地向前移动if(rI=0)(x=0)(*比较)；rj d=x；否则(*比较)；3.冒泡排序：成对比较相邻记录的关键字，如果顺序颠倒，则交换它们，直到没有颠倒顺序的记录。空气泡排序(intr ，intn，int * compare，int

4、 * move)/交换(气泡)排序* compare=0；* move=0；int x；对于(int j=0；jj；i -)如果(ri=zhou) /查看右边元素和轴之间的大小关系(*比较)；j-；如果(I使用命名空间标准；void Insertsort(int r，int n，int* compare，int * move)；void ShellInsert(int r，int n，int* compare，int * move)；void Bubblesort(int r，int n，int* compare，int * move)；int Partion(int r，int first，int end，int* compare，int * move)；void Qsort(int r，int i，int j，int* compare，int * move)；void Selectsort(int r，int n，int* compare，int * move)；void main()int I；int compare=0；int move=0；Cout 首先输入一个正序数组 n；int * r=新intn；“Cout”请在数组中输入元素