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(&