数据结构实验_.doc

《数据结构实验_.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、计算机系数据结构实验报告（7）姓名：孟红波学号：专业班级：卓越计算机101班实验目的：深入了解各种内部排序方法及效率分析。问题描述：各种内部排序算法的时间复杂度分析，试通过随机数据比较算法的关键字比较次数和关键字移动次数。实验要求：文法是一个四元1、对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序这六种常用排序算法进行比较。2、待排序表的表长不超过100；其中数据用伪随机数产生程序产生。3、至少要用6组不同的输入数据做比较。4、要对实验结果做简单分析。实验内容和过程：实验步骤1、根据问题描述写出基本算法。2、

2、设计六种排序算法并用适当语言实现。3、输入几组随机数据，并对其关键字比较次数和关键字移动次数的比较。4、对结果进行分析。5、进行总结。六种实验算法的基本思想：（1）直接插入排序的基本思想是：当插入第i个数据元素k时，由前i-1个数据元素组成已排序的数据元素序列，将k的关键字与序列中各数据元素的关键字依次进行比较后，找到该插入位置j，并将第j以及后面的数据元素顺序后移一个位置，然后将k插入到位置j，使得插入后的数据元素序列仍是排序的。（2）希尔排序的基本思想是：先将整个待排序记录序列按给定的下标增量进行分组，并对组内的记录采用直

3、接插入排序，再减小下标增量，即每组包含的记录增多，再继续对每组组内的记录采用直接插入排序；以此类推，当下标增量减小到1时，整个待排序记录已成为一组，再对全体待排序记录进行一次直接插入排序即可完成排序工作。（3）冒泡排序的基本思想是：将相邻的两个数据元素按关键字进行比较，如果反序，则交换。对于一个待排序的数据元素序列，经一趟排序后最大值数据元素移到最大位置，其它值较大的数据元素向也最终位置移动，此过程为一次起泡。然后对下面的记录重复上述过程直到过程中没有交换为止，则已完成对记录的排序。（4）选择排序的基本思想是：设有N个数据元素

4、的序列，第一趟排序，比较N个数据元素，选择关键字最小的数据元素，将其交换到序列的第1个位置上；第2趟排序，在余下的N-1个数据元素中，再选取关键字最小的数据元素，交换到序列的第2个位置上；继续进行，经过N-1趟排序，N个数据元素则按递增次序排列完成。（5）快速排序的基本思想是：在待排序记录序列中，任取其中的一个记录（这里取了第一个）并以该记录的关键字作为基准，经过一趟排序后，所有关键字比它小的记录都交换到它的左边，比它大的记录都交换到它的右边。然后再分别对划分到它的左、右两部分记录序列重复上述过程，直至每一部分最终划分为一个记

5、录时为止即完成了排序工作。（6）堆排序排序的基本思想是：在排序过程中，将记录数组R[1…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点的内在关系用筛选法将待排序的数据元素序列建成堆，得到最大值—根节点的值。将根节点值向后交换，再将余下的根调整成堆，重复进行直到排序完成。设计程序代码如下：#include#include#include#defineSIZE10//起泡排序voidBubbleSort(int*a,intsize){inti,j;i

6、nttemp;for(i=size-1;i>0;i--)for(j=0;ja[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}//直接插入voidInsertSort(int*a,intsize){inti,k;intt;for(i=1;i=0&&a[k]>t){a[k+1]=a[k];k--;}a[k+1]=t;}}//简单选择voidSelectSort(int*a,intsize){int

7、i,j;inttemp;intmin;intMinIndex;for(i=0;i

8、low=k)--high;a[low]=a[high];while(low