数据结构七个排序课程设计.doc.doc

数 据 结 构 课程设计报告 题目：排序的实现 专业：软件工程 班级：1502 学号： 姓名： 时间：2016-12-26—2017-1-6 问题描述 题目内容：排序算法实现。 基本要求：用C语言或者C++设计一个排序综合系统。 测试数据：手写输入数据。 需求分析 程序所能达到的基本功能。 设计一个菜单，格式如下： 选择排序 插入排序- 起泡排序 快速排序 归并排序 堆排序 基数排序 重新输入数据 退出 选择不同的菜单但进行相应的排序，并给出排序的关键字序列。求出该排序算法运行时间，比较各排序间效率。 输入的形式和输入值的范围：所有整型的数。 输出的形式：从小到大输出排序结果和运行时间。 测试数据要求。 输入元素个数为正整数。 输入将要排序的数都为整型。 概要设计 所需的ADT,它们的作用。 ADT SORT{ 数据对象：D=用户输入n数据元素； 基本操作： void ShuRu(SqList L); ------------------- 用户输入 Void SelectSort(SqList L)； ------------------- 选择排序 void nsertSort(SqList L); ------------------- 插入排序- void BBubbleSort(SqList L); ------------------- 起泡排序 void QuickSort(SqList L); ------------------- 快速排序 void MergeSort(SqList L); ------------------- 归并排序 void HeapSort(SqList L); ------------------- 堆排序 void RadixSort(SqList L) ------------------- 基数排序 }ADT SORT 主程序流程及模块调用关系。 核心的粗线条伪代码算法。 详细设计 实现概要设计的数据类型，重点语句加注释。 每个操作的伪代码算法，重点语句加注释。 主程序和其他模块的伪码算法，重点语句加注释。 函数调用关系图。 调试分析 设计与调用过程中遇到的问题及分析、体会。 由于是输入是手打输入，当数据少时，各排序算法运行时间都接近于0，导致时间显示几乎一样，无法进行比较各排序效率。所以在网上找了更加精细计算函数运行时间的算法。这让我懂得查找资料和思考会让你的算法更加完善。 主要和典型算法的时空复杂度的分析。 排序方法 平均时间 最坏情况 最好情况 辅助空间 稳定性 插入排序 O(n2) O(n2) O(n2) O(1) √ 选择排序 O(n2) O(n2) O(n2) O(1) √ 起泡排序 O(n2) O(n2) O(n) O(1) √ 快速排序 O(nlogn) O(n2) O(nlogn O(logn) × 归并排序 O(nlogn) O(nlogn O(nlogn O(n) √ 堆排序 O(nlogn) O(nlogn O(nlogn O(1) × 基数排序 O(d*n) O(d*n) O(d*n) O(n) √ 使用说明 简要说明程序运行操作步骤。 输入需要排序总数。 输入数据。 根据菜单选择1~8进行排序，重复进行。 输入9确定退出。 测试结果 包括输入和输出，输入集应多于需求分析的数据。 附录（带注释的源程序） #include stdio.h #include iostream #include ctime #include windows.h #include cmath using namespace std; const MAXSIZE=10000; typedef struct{ int r[MAXSIZE+1];//r[0]闲置或者作为判别标志的“哨兵”单元 int length;//顺序表的记录空间为r[1…length] }SqList;//顺序表类型 void ShuRu(SqList L,int n)//输入函数 { L.length=n; for (int i=1;i=L.length;i++) { coutr[i-1]=; cinL.r[i]; } coutendl; } void ShuChu(SqList L)//输出函数 { cout排序的结果为：