排序实验报告.doc

数据结构实验报告
排序
小组成员:
张家铭2010416648吴建明2010416603
刘仕乾2010416682王战海2010416596
1实验题目
为了更好的学习数据结构,理解排序思想,直观的观察出每一步所进行的操作。进行此实验报告。主要包含直接插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序。
2需求分析
在现在的任何pc、mac上均可装有c-Free或VC 。
输入形式,先用种子函数初始化随机生成函数,然后用随机生成函数生成十个数据。通过选择你想选用的排序方式包括:insertSort(arr,10);//插入排序shellSort(arr,3,10);//希尔排序 bubbleSort(arr,10);//冒泡排序QuickSort(arr, 1 , 11);//快速排序selectSort(arr,10);//选择排序 heapsort(arr, 10000); //堆排序
输出形式,通过调用printarr函数进行输出数据,并在排序之中调用此函数了来直观的查看排序的过程。
程序附加功能,在排序进行之前设计了开始时间(start = time(NLULL)),在排序结束之后设计了结束时间(end = time(NULL)),之后在输出该排序执行的时间(printf("执行时间为:%d\n",(end-start));)。直观的看出该程序的优劣。PS:执行小量数据体现不出时间损耗,可以设计大量数据看出时间损耗。
测试数据,随机生成,数据不定。
3概要设计
(1)包含的头文件#include <>
#include <>
#include <> 用于生成随机函数和计时用
(2)本程序包含的主要函数:
void printarr(int arr[],int n) //输出列表函数
void insertSort(int arr[],int n) //插入排序注意监视哨作用
void shellpass(int arr[],int d,int n) //希尔排序一趟 d为步长
void shellSort(int arr[],int b,int n) //希尔排序
void bubbleSort(int arr[],int n) //冒泡排序
void QuickSort(int data[], int left, int right) //快速排序重点的排序
void selectSort(int arr[],int n) //选择排序
void shift(int arr[], int i, int n) // 建堆 i为根节点 n为个数
void heapsort(int arr[], int n) //堆排序
void main() //主函数
(3)各函数之间的关系如图3-3:
图3-3 程序中各函数之间的关系
4详细设计
(1)直接插入排序,arr[0]为监视哨的作用。把未排好序的第一个数依次与已排好序的比较,寻找到合适位置插入。详细设计如下:
void insertSort(int arr[],int n) //插入排序注意监视哨作用
{
int i, j;
for (