文档介绍：2009级数据结构实验报告
实验名称: 使用链表实现各种排序算法
学生姓名: 桂柯易
班级: 2009211120
班内序号: 07
学号: 09210580
日期: 2010年12月19日
【实验目的】
通过选择实验内容中的两个题目之一,学习、实现、对比各种排序算法,掌握各种排序算法的优劣,以及各种算法的使用的情况。
【实验内容】
使用链表实现下面各种排序算法,并进行比较。
排序算法如下:
插入排序;
冒泡排序;
快速排序;
简单选择排序;
其他。
具体要求如下。
测试数据分成三类:正序、逆序、随机数据。
对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。
对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)。
对②和③的结果进行分析,验证上述各种算法的时间复杂度。
编写main()函数测试各种排序算法的正确性。
存储结构
存储结构:链表
关键算法分析
【设计思想】
以直接插入排序为例:首先将待排序数据建立一个带头结点的单链表。在单链表中进行直接插入排序的基本思想是:将单链表划分为有序区和无序区,有序区只包含一个元素节点,依次取无序区中的每一个结点,在有序区中查找待插入结点的插入位置,然后把该结点从单链表中删除,再插入到相应位置。
分析上述排序过程,需设一个工作指针q在无序区中指向待插入的结点,为了查找正确的插入位置,每趟排序前需将工作指针pre和p指向头结点和开始结点,在找到插入位置后,将结点q插在结点pre和p之间。这相当于在单链表中删除结点q,因此为了保证链表不断开,须在删除结点q之前保留结点q的后继结点的地址。
【复杂度】
(1)建立链表存储数据的算法:
Node *CreateSortNode(int count,int *array)
{
Node *p1,*p2,*head;
int i;
head=NULL;
for(i=0;i<count;i++)
{
p1=new Node;
p1->data=array[i];
p1->next=NULL;
if (i==0)
head=p1;
else
p2->next=p1;
p2=p1;
}
p2->next=NULL;
return head;
}
该算法的时间复杂度为T(N)=O(N)
(2)输出数据的算法:
void ListSortNode(Node *start)
{
Node *p;
p=start;
while(p!=NULL)
{
cout<<p->data<<'\0';
p=p->next;
}
cout<<endl;
}
该算法的时间复杂度T(N)=O(N)
(3)插入排序算法:
Node *Insert_Sort_LinkTable(Node *head)
{
_LARGE_INTEGER time_start;
_LARGE_INTEGER time_over;
double dqFreq;
LARGE_INTEGER f;
Query