include.docx
- 文档编号:17178373
- 上传时间:2023-07-22
- 格式:DOCX
- 页数:13
- 大小:16.84KB
include.docx
《include.docx》由会员分享,可在线阅读,更多相关《include.docx(13页珍藏版)》请在冰点文库上搜索。
include
#include
#include
usingnamespacestd;
structDNode//双向链表节点结构
{
intdata;//数据域
structDNode*prior;//指针域,指向前一节点
structDNode*next;//指针域,指向后一节点
};
classSort
{
public:
voidInit(intnum[],intn);//初始化双链表
voidInsertSort();//插入排序
voidBubbleSort();//冒泡排序
DNode*Partion(DNode*fiest,DNode*end);//一趟快速排序
voidQSort(DNode*a,DNode*b);//快速排序
voidSelectSort();//简单快速排序
voidprint();//打印函数
DNode*GetFirst(){returnfront->next;}
DNode*GetEnd(){returnfront->prior;}
private:
DNode*front;
intmove;
intcompare;
};
voidSort:
:
Init(intnum[],intn)//双向链表
{
front=newDNode;
front->next=front;//front的next域指向front
front->prior=front;//front的prior域指向front
DNode*r=front;//初始化工作指针
move=compare=0;
for(inti=0;i { DNode*s=newDNode;//建立新节点 s->data=num[i];//将*写入新节点的指针域 s->prior=r;//s的prior域指向r s->next=r->next;//s的next域指向r的next域 r->next->prior=s;//r的直接后继的prior域指向s r->next=s;//r的next域指向s r=r->next;//将s赋给r } } voidSort: : InsertSort()//插入排序 { DNode*p=front->next->next;//初始化工作指针,从第二个数开始 inttemp;//用于存放哨兵 while(p! =front)//如果p不是头节点 { temp=p->data;//将p赋值给哨兵 compare++;// if(temp { DNode*s=p->prior;// while(s! =front&&s->data>temp)// { s->next->data=s->data; s=s->prior; move++; compare++; } s->next->data=temp; move++; } p=p->next; } } voidSort: : BubbleSort()//冒泡排序 { DNode*r=front->prior;// while(r! =front)//当r不是头节点 { DNode*q=r;//本次无序元素的范围 r=front;//若去掉的话,正序时会死循环 DNode*p=front->next;//工作指针,每次从第一个元素开始 while(p! =q) { compare++; if(p->data>p->next->data)//如果p的数据域大于p的直接后继的数据域 { inttemp=p->data;//将p暂时赋给temp p->data=p->next->data;//将p的直接后继赋给p p->next->data=temp;//将temp赋给p的直接后继 move+=3; r=p;//记录最后一个无序序列位置 } p=p->next;// } } } DNode*Sort: : Partion(DNode*first,DNode*end)//快速排序 { DNode*p=first; DNode*r=end; intpivot=p->data; while(p! =r) { while((p! =r)&&(r->data>=pivot)) { compare++; r=r->prior; } p->data=r->data; move++; while((p! =r)&&(r->data<=pivot)) { compare++; p=p->next; } r->data=p->data; move++; } p->data=pivot; returnp; } voidSort: : QSort(DNode*a,DNode*b) { if(a! =b) { DNode*pivotloc=Partion(a,b); if(pivotloc! =a) QSort(a,pivotloc->prior); if(pivotloc! =b) QSort(pivotloc->next,b); } } voidSort: : SelectSort() { DNode*p=front->next; while(p! =front->prior) { DNode*s=p; DNode*temp=p->next; while(temp! =front) { compare++; if(temp->data s=temp; temp=temp->next; } if(s! =p) { intm=p->data; p->data=s->data; s->data=m; move+=3; } p=p->next; } } voidSort: : print() { DNode*p=front->next; cout<<"排序后的数据为: \n"; while(p! =front) { cout< p=p->next; } cout< cout<<"比较次数为: "< cout<<"移动次数为: "< } voidmain() { intnum1[20]={1,2,3,4,5,6,7,8,9,10,11,20,13,14,15,16,17,18,19,20}; intnum2[20]={20,19,18,17,16,15,14,13,20,11,10,9,8,7,6,5,4,3,2,1}; intnum3[20]={20,34,11,87,67,45,9,49,101,67,55,200,14,16,84,34,27,59,98,47}; Sorta; LARGE_INTEGERbegin,end,feq; cout<<"【正序测试数据】: "; for(inti=0;i<20;i++) cout< cout< cout<<"<插入排序>: \n"; a.Init(num1,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.InsertSort(); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout<<"<冒泡排序>: \n"; a.Init(num1,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.BubbleSort(); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout<<"<快速排序>: \n"; a.Init(num1,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.QSort(a.GetFirst(),a.GetEnd()); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout<<"<简单选择排序>: \n"; a.Init(num1,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.SelectSort(); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout< cout<<"【逆序测试数据】: "; for(inti=0;i<20;i++) cout< cout< cout<<"<插入排序>: \n"; a.Init(num2,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.InsertSort(); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout<<"<冒泡排序>: \n"; a.Init(num2,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.BubbleSort(); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout<<"<快速排序>: \n"; a.Init(num2,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.QSort(a.GetFirst(),a.GetEnd()); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout<<"<简单选择排序>: \n"; a.Init(num2,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.SelectSort(); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout< cout<<"【随机测试数据】: "; for(inti=0;i<20;i++) cout< cout< cout<<"<插入排序>: \n"; a.Init(num3,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.InsertSort(); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout<<"<冒泡排序>: \n"; a.Init(num3,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.BubbleSort(); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout<<"<快速排序>: \n"; a.Init(num3,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.QSort(a.GetFirst(),a.GetEnd()); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< cout<<"<简单选择排序>: \n"; a.Init(num3,20); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&begin); a.SelectSort(); QueryPerformanceCounter(&end); a.print(); cout<<"运行时间: " <<((double)end.QuadPart-(double)begin.QuadPart)*1000000/((double)feq.QuadPart) <<"us"< system("pause"); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- include