1．实验要求
i.实验目的:
通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。
理解算法的主要思想及流程。
ii.实验内容：
使用链表实现下面各种排序算法，并进行比较。
排序算法：
1、插入排序
2、冒泡排序（改进型冒泡排序）
3、快速排序
4、简单选择排序
5、堆排序（小根堆）
要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次
移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性
iii.代码要求：
1、必须要有异常处理，比如删除空链表时需要抛出异常；
2、保持良好的编程的风格：
代码段与段之间要有空行和缩近
标识符名称应该与其代表的意义一致
函数名之前应该添加注释说明该函数的功能
关键代码应说明其功能
3、递归程序注意调用的过程，防止栈溢出
2. 程序分析
通过排序算法将单链表中的数据进行由小至大（正向排序）
2.1 存储结构
单链表存储数据： struct node {
int data;
node *next;
};
单链表定义如下：
class LinkList {
private :
node * front; public :
LinkList(int a[], int n);//构造
~LinkList();
void insert(node *p, node *s);//插入
void turn(node *p, node *s);//交换数据
void print();//输出
void InsertSort();//插入排序
void BubbleSort();//pos 冒泡
void QSort();//快速排序
void SelectSort();//简单选择排序
node * Get(int i);
//查找位置为i 的结点
void sift(int k, int m); //一趟堆排序
void LinkList ::QSZ(node * b, node *e); //快速排序的递归主体
void heapsort(int n); //堆排序算法
};
2.2 关键算法分析：
1.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。
分析上述排序过程，需设一个工作指针p->next 在无序区中指向待插入的结点，在找到插入位置后，将结点p->next 插在结点s 和p 之间。
void LinkList ::InsertSort()//将第一个元素定为初始有序区元素，由第二个元素开始依次比较
{
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); //每秒跳动次数
QueryPerformanceCounter(&t1); //测前跳动次数
node * p = front->next;//要插入的节点的前驱
……
{
node * s = front;//充分利用带头结点的单链表
while (1)
{
comparef++;
if (p->next->data next->data)// [P后继]比[S后继]小则插入
{
insert(p, s); break;
}
s = s->next;
if (s == p)//若一趟比较结束，且不需要插入
{
p = p->next; break;
}
}
}
QueryPerformanceCounter(&t2); //测后跳动次数
double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒cout << "操作时间为：" << d << endl;
}
2.快速排序：
主要通过轴值将数据从两端向中间进行比较，交换以实现排序。
通过递归的调用来实现整个链表数据的排序。
代码中选用了第一个元素作为轴值。
一趟排序的代码：
void LinkList::QSZ(node * b, node *e)
{
if (b->next == e || b == e)//排序完成
return;
node * qianqu = b;//轴点前驱
node * p = qianqu->next;
while (p != e && p != e->next)
{
comparef++;
if (qianqu->next->data > p->next->data)//元素值小于轴点值，则将该元素插在轴点之前{
if (p->next == e)//若该元素为e，则将其前驱设为e
e = p;
insert(p, qianqu);
qianqu = qianqu->next;
}
else p = p->next;
}
QSZ(b, qianqu);//继续处理轴点左侧链表
QSZ(qianqu->next, e);//继续处理轴点右侧链表
