c语言内部排序实验报告,内部排序算法比较实验报告(c语言版)

题目&＃xff1a;编制一个演示内部排序算法比较的程序

班级&＃xff1a;姓名&＃xff1a;学号&＃xff1a;完成日期&＃xff1a;

一、需求分析

1&＃xff0e;本演示程序对以下6种常用的内部排序算法进行实测比较&＃xff1a;起泡排序&＃xff0c;直接插入排序&＃xff0c;简单选择排序&＃xff0c;快速排序&＃xff0c;希尔排序&＃xff0c;堆排序。

2&＃xff0e;待排序表的元素的关键字为整数。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换记为3次移动)。

3&＃xff0e;演示程序以以用户和计算机的对话方式执行&＃xff0c;在计算机终端上显示提示信息&＃xff0c;对随机数组进行排序&＃xff0c;并输出比较指标值。

4&＃xff0e;最后对结果作出简单分析。

二、概要设计

1&＃xff0e;可排序表的抽象数据类型定义&＃xff1a;

ADT OrderableList{

数据对象&＃xff1a;D&＃61;{ai|ai∈IntegerSet,i&＃61;1,2,…,n,n≥0}

数据关系&＃xff1a;R1&＃61;{|ai-1,ai∈D,i&＃61;2,…,n}

基本操作&＃xff1a;

InitList(n)

操作结果&＃xff1a;构造一个长度为n&＃xff0c;元素值依次为1&＃xff0c;2&＃xff0c;…,n的有序表。

RandomizeList(d,isInverseOrder)

操作结果&＃xff1a;首先根据isInverseOrder为True或False,将表置为逆序或正序&＃xff0c;然后将表进行d(0≤d≤8)级随机打乱。d为0时表不打乱&＃xff0c;d越大&＃xff0c;打乱程度越高。

RecallList()

操作结果&＃xff1a;恢复最后一次用RandomizeList随机打乱得到的可排序表。

ListLength()

操作结果&＃xff1a;返回可排序表的长度。

ListEmpty()

操作结果&＃xff1a;若可排序表为空表&＃xff0c;则返回Ture&＃xff0c;否则返回False。

BubbleSort( &c, &s)

操作结果&＃xff1a;进行起泡排序&＃xff0c;返回关键字比较次数c和移动次数s。

InsertSort( &c, &s)

操作结果&＃xff1a;进行插入排序&＃xff0c;返回关键字比较次数c和移动次数s。

SelectSort ( &c, &s)

操作结果&＃xff1a;进行选择排序&＃xff0c;返回关键字比较次数c和移动次数s。

QuickSort(&c, &s)

操作结果&＃xff1a;进行快速排序&＃xff0c;返回关键字比较次数c和移动次数s。

ShellSort(long &c, long &s)

操作结果&＃xff1a;进行希尔排序&＃xff0c;返回关键字比较次数c和移动次数s。

HeapSort (&c, &s)

操作结果&＃xff1a;进行堆排序&＃xff0c;返回关键字比较次数c和移动次数s。

ListTraverse(visit())

word文档可自由复制编辑