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

数据结构实验报告

实验名称： 学生姓名： 班 级： 班内序号： 学 号： 日 期：

实验描述：使用链表实现下面各种排序算法，并进行比较。

排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 一．程序分析

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.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

c)快速排序：一趟快速排序的算法是：

1.设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2.以第一个数组元素作为关键数据，赋值给key，即key=A[0]； 3.从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

4.从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

5.重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于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 #include 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 SeqSort(); //插入排序 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;idata=a[i]; rear->next=s; s->last=rear; rear=s; } }

void 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<data<<\ p=p->next; } cout<

void List::Delete(Node* p) { 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_interger.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=1; break; } q=q->next; } p=p->next; if(ifdelete==1) { Delete(De); } }

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

void List::BubSort() //冒泡排序 {

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; Node* q=rear; int temp; int j; for(j=0;jnext; 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->last; }

QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart;