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; //要插入的节点的前驱 while (p->next) { node * s = front; //充分利用带头结点的单链表 while (1) {
comparef++; if (p->next->data
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); //继续处理轴点右侧链表
}
整个快速排序的实现: void LinkList::QSort() { LARGE_INTEGER t1, t2, feq; QueryPerformanceFrequency(&feq); //每秒跳动次数 QueryPerformanceCounter(&t1); //测前跳动次数 node * e = front; while (e->next) { e = e->next; } QSZ(front, e); QueryPerformanceCounter(&t2); //测后跳动次数 double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒 cout << \操作时间为：\ << d << endl; }
3.改进版的冒泡排序：
通过设置pos来记录无序边界的位置以减少比较次数。
将数据从前向后两两比较，遇到顺序不对是直接交换两数据的值。 每交换一次movef+3； void LinkList::BubbleSort() { LARGE_INTEGER t1, t2, feq; QueryPerformanceFrequency(&feq); //每秒跳动次数 QueryPerformanceCounter(&t1); //测前跳动次数 node * p = front->next; while (p->next) // 排序查找无序边界 { comparef++; if (p->data > p->next->data) turn(p, p->next); p = p->next; } node * pos = p; p = front->next; while (pos != front->next) { node * bound = pos; pos = front->next; while (p->next != bound) { comparef++;
if (p->data > p->next->data) { turn(p, p->next); pos = p->next; } p = p->next; } p = front->next; } QueryPerformanceCounter(&t2); //测后跳动次数 double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒 cout << \操作时间为：\ << d << endl; }
4.选择排序：
每趟排序再待排序的序列中选择关键码最小的元素，顺序添加至已排好的有序序列最后，知道全部记录排序完毕。 void LinkList::SelectSort() { LARGE_INTEGER t1, t2, feq; QueryPerformanceFrequency(&feq); //每秒跳动次数 QueryPerformanceCounter(&t1); //测前跳动次数 node * s = front; while (s->next->next) { node * p = s; node * index = p; while (p->next) { comparef++; if (p->next->data < index->next->data) index = p; p = p->next; } insert(index, s); s = s->next; } QueryPerformanceCounter(&t2); //测后跳动次数 double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒 cout << \操作时间为：\ << d << endl; }
5.堆排序：
利用前一趟比较的结果来减少比较次数，提高整体的效率。
c数据结构实验链表排序
