c++数据结构实验链表排序

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.堆排序：

利用前一趟比较的结果来减少比较次数，提高整体的效率。

其中通过链表储存了一棵树。 选择使用小根堆进行排序。 void LinkList::sift(int k, int m) { int i = k, j = 2 * i; while (j <= m) { comparef++; if (jdata>Get(j + 1)->data)) j++; if (Get(i)->data < Get(j)->data) break; else { turn(Get(i), Get(j)); i = j; j = 2 * i; } } }

void LinkList::heapsort(int n) { LARGE_INTEGER t1, t2, feq; QueryPerformanceFrequency(&feq); //每秒跳动次数 QueryPerformanceCounter(&t1); //测前跳动次数 for (int i = n / 2; i >= 1; i--) sift(i, n); for (int i = 1; i < n; i++) { turn(Get(1), Get(n - i + 1)); sift(1, n - i); } QueryPerformanceCounter(&t2); //测后跳动次数 double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒 cout << \操作时间为：\ << d << endl; }

其中堆排序中需要知道孩子节点和父亲节点处的值，故设置了函数获取i出的指针。 node*LinkList::Get(int i) { node*p = front->next; int j = 1; while (j != i&&p) { p = p->next;

}

j++;

if (!p) throw \查找位置非法\; else return p; };

6.输出结果的函数：

void tell(LinkList &a, LinkList &b, LinkList &c, LinkList &d, LinkList &e) { a.print(); comparef = 0; movef = 0; a.InsertSort(); cout << \排序结果：\; a.print(); cout << \插入排序法： Compare：\ << setw(3) << comparef << \ Move：\ << setw(3) << movef << endl; comparef = 0; movef = 0; b.BubbleSort(); cout << \改进型冒泡排序法： Compare：\ << setw(3) << comparef << \ Move：\ << setw(3) << movef << endl; comparef = 0; movef = 0; c.QSort(); cout << \快速排序法： Compare：\ << setw(3) << comparef << \ Move：\ << setw(3) << movef << endl; comparef = 0; movef = 0; d.SelectSort(); cout << \简单选择排序法 Compare：\ << setw(3) << comparef << \ Move：\ << setw(3) << movef << endl; comparef = 0; movef = 0; e.heapsort(10); cout << \堆排序算法 Compare：\ << setw(3) << comparef << \ Move：\ << setw(3) << movef << endl; }

7.统计时间的函数： #include {

LARGE_INTEGER t1, t2, feq; QueryPerformanceFrequency(&feq); //每秒跳动次数

QueryPerformanceCounter(&t1); //测前跳动次数 node * p = front->next; //要插入的节点的前驱

QueryPerformanceCounter(&t2); //测后跳动次数 double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒

cout << \操作时间为：\ << d << endl; };

2.3 其他

算法的时间复杂度： 排序方法 直接插入排序 快速排序 改进版冒泡排序 选择排序 堆排序 随机序列的平均情况 O(n2) 最好情况 O(n) 最坏情况 O(n2) O(n2) O(n2) O(n2) 辅助空间 O(1) O(nlog2n) O(n2) O(n2) O(nlog2n) O (n) O(n2) O(log2n) ~O(n) O(1) O(1) O(nlog2n) O(nlog2n) O (nlog2n) O(1) 3. 程序运行结果

1.流程图：

开始 初始化正序链表，调用各类排序，并输出运行结果 初始化逆序链表，调用各类排序，并输出运行结果 初始化顺序随机的链表，调用各类排序，并输出运行结果 结 束