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

1、数据结构实验报告实验名称： 学生姓名： 班 级： 班内序号： 学 号： 日 期： 实验描述：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他1 程序分析 1.存储结构：双向链表 2.关键算法分析：a)插入排序：从有序数列和无序数列a2,a3，an开始进行排序； 处理第i个元素时（i=2,3，n），数列a1,a2，ai-1是已有序的，而数列ai,ai+1，an是无序的。用ai与ai-1，a i-2，a1进行比较，找出合适的位置将ai插入； 重复第二步，共进行n-i次插入处理，数列全部有序。b)冒泡排序： 1.比较相邻的元素。如果第一

2、个比第二个大，就交换他们两个。 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤，除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。c)快速排序：一趟快速排序的算法是： 1.设置两个变量i、j，排序开始的时候：i=0，j=N-1； 2.以第一个数组元素作为关键数据，赋值给key，即key=A0； 3.从j开始向前搜索，即由后开始向前搜索(j-)，找到第一个小于key的值Aj，将Aj和Ai互换； 4.从i开始向后搜索，即由前开始向后搜索(i+)，找到第一个大于key的A

3、i，将Ai和Aj互换； 5.重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中Aj不小于key,4中Ai不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i=j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。d)简单选择排序：设所排序序列的记录个数为n。i取1,2,n-1,从所有n-i+1个记录（Ri,Ri+1,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。 3.代码详细分析：#include<iostream>#includ

4、e<windows.h> using namespace std;struct Node /建立节点 int data;Node* last;Node* next;Node()last=NULL;next=NULL; class List /建立链表 private:Node* front;Node* rear;int length;public: List();List(int a,int n); void Insert(int x,Node* p); /在p后面插入节点 void Delete(Node* p); /删除p节点 void Print(); /打印 void Se

5、qSort(); /插入排序 void BubSort(); /冒泡排序 void QuiSort(); /快速排序 void Qui(Node* first,Node* end,int* c); /快速排序的递归函数 void SelSort(); /简单选择排序 ;List:List(int a,int n) /构造函数 front=new Node;length=n;rear=front;int i;Node* s; for(i=0;i<n;i+)s=new Node;s->data=ai;rear->next=s;s->last=rear;rear=s;void

6、 List:Insert(int x,Node* p) /插入函数 Node* s=new Node;s->data=x;s->last=p->last;p->last->next=s;p->last=s;s->next=p; void List:Print() /打印函数 Node* p=front->next;while(p!=NULL)cout<<p->data<<" "p=p->next;cout<<endl;void List:Delete(Node* p) /删除函数

7、 Node* De=p;if(p=rear)rear=p->last;p->last->next=NULL;delete De;else p->last->next=p->next; p->next->last=p->last; delete De;void List:SeqSort() /插入排序 LARGE_INTEGER large_interger; double dff; _int64 c1, c2; QueryPerformanceFrequency(&large_interger); dff = large_inter

8、ger.QuadPart; QueryPerformanceCounter(&large_interger); c1 = large_interger.QuadPart;int ccom=0; int cmove=0;Node* p=front->next->next;Node* q;Node* De;bool ifdelete;while(p!=NULL)ifdelete=0;q=front->next;while(q!=p) ccom+;if(q->data>=p->data)De=p;Insert(p->data,q);ifdelete=

9、1;break;q=q->next;p=p->next;if(ifdelete=1)Delete(De);QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; cout<<"SeqSort:"Print();cout<<"比较次数："<<ccom<<endl;cout<<"移动次数："<<cmove<<endl;cout<<&quo

10、t;用时："<<(c2 - c1) * 1000*1000/dff<<"微秒"<<endl; cout<<endl;void List:BubSort() /冒泡排序 LARGE_INTEGER large_interger; double dff; _int64 c1, c2; QueryPerformanceFrequency(&large_interger); dff = large_interger.QuadPart; QueryPerformanceCounter(&large_interg

11、er); c1 = large_interger.QuadPart; int ccom=0; int cmove=0;Node* p;Node* q=rear;int temp;int j;for(j=0;j<length-1;j+) p=front->next; while(p!=q) ccom+; if(p->data>p->next->data) temp=p->next->data; p->next->data=p->data; p->data=temp; cmove+=3; p=p->next; q=q-&

12、gt;last; QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; cout<<"BubSort:" Print();cout<<"比较次数："<<ccom<<endl;cout<<"移动次数："<<cmove<<endl;cout<<"用时："<<(c2 - c1) * 1000*1000/dff<&

13、lt;"微秒"<<endl; cout<<endl;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;c0+;c0+;p1->data=p2->data;c1+;while(p1!=p2&p1->data<=pivot)p1=p

14、1->next;c0+;c0+;p2->data=p1->data;c1+;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; QueryPerformanceFrequenc

15、y(&large_interger); dff = large_interger.QuadPart; QueryPerformanceCounter(&large_interger); c1 = large_interger.QuadPart; int count2=0;Qui(front->next,rear,count);QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; cout<<"QuiSort:"Print();cout<&

16、lt;"比较次数："<<count0<<endl;cout<<"移动次数："<<count1<<endl;cout<<"用时："<<(c2 - c1) * 1000*1000/dff<<"微秒"<<endl; cout<<endl;void List:SelSort() /简单选择排序 LARGE_INTEGER large_interger; double dff; _int64 c1, c2;

17、 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->data<p->data)temp=q->dat

18、a;q->data=p->data;p->data=temp; cmove+=3;q=q->last;p=p->next;QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; cout<<"SelSort:" Print();cout<<"比较次数："<<ccom<<endl;cout<<"移动次数："<<cmove<<end

19、l;cout<<"用时："<<(c2 - c1) * 1000*1000/dff<<"微秒"<<endl; cout<<endl;main()const int n=5;int an;cout<<"输入一组"<<n<<"个数据："<<endl; int i;for(i=0;i<n;i+)cin>>ai;List L1(a,n);List L2(a,n);List L3(a,n);List L4(a,n); int Menu;while(1) cout<<"Menu:"<<endl; cout<<"1.插入排序"<<endl; cout<<"2.冒泡排序"&l