北邮数据结构实验四链表排序研讨.doc

数据结构实验报告 实验名称： 学生姓名： 班 级： 班内序号： 学 号： 日 期： 实验描述：使用链表实现下面各种排序算法，并进行比较。 排序算法： 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.代码详细分析： #includeiostream #includewindows.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 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;in;i++) { s=new Node; s-data=a[i]; rear-next=s; s-last