1．实验要求
i.
实验目的:
通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。
理解算法的主要思想及流程。
ii. 实验内容：
使用链表实现下面各种排序算法，并进行比较。 排序算法：
1、插入排序
2、冒泡排序（改进型冒泡排序） 3、快速排序 4、简单选择排序 5、堆排序（小根堆） 要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性
iii. 代码要求：
1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格：
代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能
3、递归程序注意调用的过程，防止栈溢出
2. 程序分析
通过排序算法将单链表中的数据进行由小至大（正向排序）
存储结构
单链表存储数据：
struct node { };
单链表定义如下： class LinkList { private:
node * front; int data; node*next;
……
public:
LinkList(int a[], int n);
接插入排序：首先将待排序数据建立一个带头结点
的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。
分析上述排序过程，需设一个工作指针p->next在无序区中指向待插入的结点，在找
到插入位置后，将结点p->next插在结点s和p之间。
void LinkList::InsertSort()
速排序：
主要通过轴值将数据从两端向中间进行比较，交换以实现排序。 通过递归的调用来实现整个链表数据的排序。 代码中选用了第一个元素作为轴值。 一趟排序的代码：
void LinkList::QSZ(node * b, node *e) {
if (b->next == e || b == e)
进版的冒泡排序：
通过设置pos来记录无序边界的位置以减少比较次数。
将数据从前向后两两比较，遇到顺序不对是直接交换两数据的值。 每交换一次movef+3； void LinkList::BubbleSort() {
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); 择排序：
每趟排序再待排序的序列中选择关键码最小的元素，顺序添加至已排好的有序序列最后，知道全部记录排序完毕。 void LinkList::SelectSort() {
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); 排序： 利用前一趟比较的结果来减少比较次数，提高整体的效率。 其中通过链表储存了一棵树。 选择使用小根堆进行排序。 void LinkList::sift(int k, int m)
{ }
void LinkList::heapsort(int n) {
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); 出结果的函数：
void tell(LinkList &a, LinkList &b, LinkList &c, LinkList &d, LinkList &e) {
();
comparef = 0; movef = 0; ();
cout << \排序结果：\; ();
cout << \插入排序法： Compare：\ << setw(3) << comparef << \：\ int i = k, j = 2 * i; while (j <= m) { }
comparef++;
if (j
turn(Get(i), Get(j)); i = j; j = 2 * i;
<< setw(3) << movef << endl;
comparef = 0; movef = 0; ();
cout << \改进型冒泡排序法： Compare：\ << setw(3) << comparef << \
Move：\ << setw(3) << movef << endl;
comparef = 0; movef = 0; ();
cout << \快速排序法： Compare：\ << setw(3) << comparef << \：\
<< setw(3) << movef << endl;
comparef = 0; movef = 0; ();
cout << \简单选择排序法 Compare：\ << setw(3) << comparef << \：
\ << setw(3) << movef << endl;
comparef = 0; movef = 0; (10);
cout << \堆排序算法 Compare：\ << setw(3) << comparef << \：\ <<
setw(3) << movef << endl; }
7.统计时间的函数： #include<> {
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq);
c++数据结构实验链表排序
