北邮数据结构实验四链表排序(2)

cout<<\ Print(); cout<<\比较次数：\ cout<<\移动次数：\ cout<<\用时：\微秒\ cout<

void List::Qui(Node* first,Node* end,int* c) //快速排序（有参数） { Node* p1=first; Node* p2=end; int pivot=p1->data; while(p1!=p2) { while(p1!=p2&p2->data>=pivot) { p2=p2->last;c[0]++; } c[0]++; p1->data=p2->data;c[1]++; while(p1!=p2&p1->data<=pivot) { p1=p1->next;c[0]++; } c[0]++; p2->data=p1->data;c[1]++; } p1->data=pivot; if(p1->last!=first&p1!=first)Qui(first,p1->last,c); if(p2->next!=end&&p2!=end)Qui(p1->next,end,c); }

void List::QuiSort() //快速排序（转化为无参） { LARGE_INTEGER large_interger; double dff;

__int64 c1, c2;

QueryPerformanceFrequency(&large_interger); dff = large_interger.QuadPart;

QueryPerformanceCounter(&large_interger); c1 = large_interger.QuadPart; int count[2]={0}; Qui(front->next,rear,count); QueryPerformanceCounter(&large_interger);

c2 = large_interger.QuadPart; cout<<\ Print(); cout<<\比较次数：\ cout<<\移动次数：\ cout<<\用时：\微秒\ cout<

void List::SelSort() //简单选择排序 { LARGE_INTEGER large_interger; double dff;

__int64 c1, c2;

QueryPerformanceFrequency(&large_interger); dff = large_interger.QuadPart;

QueryPerformanceCounter(&large_interger); c1 = large_interger.QuadPart; int ccom=0; int cmove=0; Node* p=front->next; Node* q; int temp; while(p!=rear) { q=rear; while(q!=p) { ccom++; if(q->datadata) { temp=q->data; q->data=p->data; p->data=temp; cmove+=3; } q=q->last; } p=p->next; } QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; cout<<\ Print(); cout<<\比较次数：\

cout<<\移动次数：\ cout<<\用时：\微秒\ cout<

main() { const int n=5; int a[n]; cout<<\输入一组\个数据：\ int i; for(i=0;i>a[i]; List L1(a,n); List L2(a,n); List L3(a,n); List L4(a,n); int Menu; while(1) { cout<<\ cout<<\插入排序\ cout<<\冒泡排序\ cout<<\快速排序\ cout<<\简单选择排序\ cout<<\各种排序方法比较\ cout<<\结束程序\ cin>>Menu; switch(Menu) { case 1:L1.SeqSort(); break; case 2:L2.BubSort(); break; case 3:L3.QuiSort(); break; case 4:L4.SelSort(); break; case 5:L1.SeqSort(); L2.BubSort(); L3.QuiSort(); L4.SelSort(); break; case 6:goto END; default:cout<<\指令错误!\

} }

END:; }

4.时间复杂度计算：

a）插入排序:O(n2) b）冒泡排序:O(n2) c）快速排序:O(nlog2n) d）简单选择排序:O(n2) 二.程序运行结果

1.测试主函数流程：

三.总结 1.问题：

A)如何用链表实现各种排序算法

B)链表的排序算法与顺序结构的排序算法有何不同 2.心得体会：

A)了解各种排序算法的本质 B)总结链表的使用方法