几种排序的实验报告

本科学生综合性实验报告数据结构课程设计学号0103917 姓名朱墨专业软件工程班级软件103实验项目名称排序算法分析指导教师涂保东开课学期2011 至2012 学年第二学期一、实验设计方案实验名称：排序算法分析实验时间：3月10~3月14日实验场地：寝室软件环境：vs20101、实验任务与目的（简单介绍实验内容，说明实验任务和目的）（1）实现四种排序（2）分析这四种排序的时间复杂度—————————————————————————————————————2、实验思路（详细描述解决问题的整体思路、涉及的算法思想及数据结构等）（1）快速排序：可以通过栈来实现，使用栈来存储排序数组的两端的下标，用来实现递归的效果。

在快排的功能函数中定义一个储存数据的数组，一个栈，一个整形变量用来储存站定的位置。

通过使用构造函数来初始化，给待排序数组赋值。

最关键的一部分是quickSort()函数，在解释这个函数之前我就先解释一下我快排的思路。

实现快排主要使用的是一个分治的策略。

将一个数组分为两部分，在中间有一个轴，要使得左边的数全部小于这个值，右边的数全部大于这个值，这就是分的部分。

治就是在说把左右两边的数组再次以相同的方式分出一共四段。

由此下去直到某个数组中只剩下一个或两、三个成员为止，之所以两、三个成员也行，是因为如果只有两个，那么这两个一定是已经拍好了序的，因为左边必定小于中间的，右边的必定大于中间的，这是比较重要的一次剪枝（可以加快1、2毫秒），而分治的方法我的和书上的有所不同，在一个数组中把第一个当作是枢轴，定义一个整形i记录第一个数的下标（从这个下标开始到其左边的直到枢轴的数都是小于等于枢轴的，包括枢轴，再定义一个整形j初始值为i+1，表示从这个值开始到数组尾都是未知是小于还是大于枢轴的。

才分值得过程中，每次都把i+1的值和枢轴比较大小，如果大于枢轴，j自加1；反之交换i+1和j，并同时自加i和j。

最把分出的两段数组的头和尾分别入栈。

下面来分析一下快排的时间复杂度，先来看一下需要分治的次数，假设数组的长度为16，那么，第一次分为8+8，第二次分为4+4+4+4，第三次2+2+2+2+2+2+2+2，第四次为 1+1+1+1+1+1+1+1+1+1+1+1+1+1；那么大致就是log216，所以分治次数为log2N，每一次分治要进行N次处理，那么平均时间复杂度为N*log2N，然后在考虑剪枝的情况，若只要分成长度小于3的时候就停下来那么只需要两次就行，也就是说只要N*[（log2N）-2]次即可。

做一次50000个数字的快排大概是12ms，可以说快速排序是一种比较优化的排序。

（1）堆排序：堆排序分为两个步骤，1、构造大（小）顶堆；2、不断的修改和交换构造大（小）顶堆。

首先来介绍一下我的构造堆的部分，大顶堆说白了就是一棵二叉树，这棵树满足的条件就是：对于每一个节点来说，他的每一个个孩子都必须小于自己。

那么我构造这棵树的方法就是，从第MAXN/2个节点开始搜索看其是否大于两个儿子（从MAXN/2开始就是一次剪枝，因为第MAXN/2+1个儿子是不可能会有子节点的），如果大于分析前MAXN/2-1个，反之把所有儿子中偏大的一个和自己交换，然后重新从第MAXN/2个开始，直到进行到根节点不用交换为止。

到此一个大顶堆就算建立完成了。

现在就是第二部分，交换和重建建堆的过程，首先一直一个大顶堆的树根一定是最大的，那么把树根和最后一个一个节点交换，最后一个叶子节点就是做大的了，接下来就是重新构造大顶堆，既从树根开始和两个儿子比较，如果小于某个儿子，在与两个儿子中最大的交换。

在以被交换的儿子为根，与其儿子比较，直到比两个儿子都大或者没儿子为止，这时数组长度减一。

完成这些操作之后，另一个大顶堆就建好了，就可进行再次的交换。

下面再来分析一下时间复杂度，先分析交换和重驻树，树的高度是log2N，若每次都从树根到底进行构造，那么一共还要进行Nlog2N次遍历。

现在再看构造初始树的部分，一共是(n^2)/4次？（这个我不太清楚。

）。

但说可以说堆排序比快排花费时间一定是更多的！（3）冒泡排序可以说是最简单的一种排序，思路就是把最大的沉底，小的浮上来。

一共进行n-1轮，每轮都是选出最大的数往后放，每个数和下个数进行比较。

时间复杂度也很好分析，一共n-1轮，最后一轮1次，第一轮n-1次，（n-1+1）*（n-1）/2，约等于n^2，可以说效率非常低。

（4）插入排序也是一种非常简单的排序，一边检索，一边构造数组，由于这题我是用链表写的，所以效率非常低。

检索一个数组，每找到一个数，便插入到链表的相应位置。

最后使链表呈现一个有序数列。

时间复杂度任然是n^2。

二、实验结果与分析1、程序结构（程序结构图，主要函数的功能描述，算法实现的细节等）主函数：主要是调用随机构造数据函数，快排，堆排，插入，冒泡的；随机函数：随机生成50000个数字，并输入到文件；快排：（1）栈·····void push(int s,int e){startPos = s;endPos = e;}Stack* pop(){return this;}(2)分治过程while(unknowFlag <= end){if(num[unknowFlag] < num[start]){//swap(num[smallFlag+1],num[unknowFlag]);temp=num[smallFlag+1];num[smallFlag+1]=num[unknowFlag];num[unknowFlag]=temp;smallFlag++;unknowFlag++;continue;}else{unknowFlag++;continue;}}（3）剪枝条件if(mid - start > 2){stack[top].push(start,mid);top++;}if(end - mid+1 > 2){stack[top].push(mid+1,end);top++;}堆排序（1）构造堆void buildHeap(int N){int p = N/2;int m,temp;while(p>0){if(2*p == N){if(num[p]>num[2*p]){temp = num[p];num[p] = num[2*p];num[2*p] = temp;}p--;continue;}else{if(num[2*p]>num[p]&&num[2*p+1]>num[p]){p--;continue;}if(num[2*p]>num[2*p+1]){if(num[2*p+1] < num[p]){temp = num[p];num[p] = num[2*p+1];num[2*p+1] = temp;m = 2*p+1;while(m<=N/2){if(2*m == N){if(num[m]>num[2*m]){temp = num[m];num[m] = num[2*m];num[2*m] = temp;}break;}else{if(num[2*m]>=num[2*m+1]){if(num[2*m+1] < num[m]){temp = num[m];num[m] = num[2*m+1];num[2*m+1] = temp;m = 2*m+1;continue;}break;}else{if(num[2*m] < num[m]){temp = num[m];num[m] = num[2*m];num[2*m] = temp;m = 2*m;continue;}break;}}}}p--;continue;}else{if(num[2*p]>num[p]&&num[2*p+1]>num[p]){p--;continue;}if(num[2*p] < num[p]){temp = num[p];num[p] = num[2*p];num[2*p] = temp;m = 2*p;while(m<=N/2){if(2*m == N){if(num[m]>num[2*m])temp = num[m];num[m] = num[2*m];num[2*m] = temp;break;}else{if(num[2*m]>=num[2*m+1]){if(num[2*m+1] < num[m]){temp = num[m];num[m] = num[2*m+1];num[2*m+1] = temp;m = 2*m+1;continue;}break;}else{if(num[2*m] < num[m]){temp = num[m];num[m] = num[2*m];num[2*m] = temp;m = 2*m;continue;}break;}}}}p--;continue;}}}}（2）交换，建堆void heapSort(int N){int temp;int i=1;temp = num[i];num[i] = num[N+1];num[N+1] = temp;while(2*i <= N){if(2*i == N)if(num[i] > num[2*i]){temp = num[i];num[i] = num[2*i];num[2*i] = temp;i = 2*i;continue;}elsebreak;else{if(num[2*i] < num[2*i+1]){if(num[i] > num[2*i]){temp = num[i];num[i] = num[2*i];num[2*i] = temp;i = 2*i;continue;}elsebreak;}else{if(num[i] > num[2*i+1]){temp = num[i];num[i] = num[2*i+1];num[2*i+1] = temp;i = 2*i+1;continue;}elsebreak;}}}}冒泡排序：void sort(){int i,j;time_t start,end,time;start=clock();for(i=1;i<MAXN-1;i++){for(j=1;j<MAXN-1-i;j++){if(num[j]>num[j+1]){int temp = num[j];num[j] = num[j+1];num[j+1] = temp;}}}插入排序：（1）链表头class sortArray{public:int date;sortArray *next;sortArray(){next = NULL;}};（2）实现插入排序：head = new sortArray();head->date = num[1];head->next = NULL;for(int i=2;i<MAXN;i++){q = head;if(num[i] <= q->date){p = new sortArray();p->date = num[i];p->next = q;head = p;continue;}else{while(1){if(q->next == NULL){q->next = new sortArray();q = q->next;q->date = num[i];break;}if(q->next->date >= num[i]){p = new sortArray();p->next = q->next;q->next = p;p->date = num[i];break;}q = q->next;}}}——————————————————————————————————————2、测试设计与数据（设计充足合理的测试用例，说明测试策略）测试数据生成：class sortDate{public :sortDate(){ofstream outfile("date.txt",ios::out);srand(time(NULL));for(int i = 1;i<MAXN;i++)outfile<<rand()%100000<<" ";//outfile.close();}};——————————————————————————————————————3、实验现象及结果（应用文字和程序运行的截图说明测试现象，并解释结果）堆排序：快排：冒泡：插入：——————————————————————————————————————4、实验分析与探讨（对测试现象和观察结果进行分析，探讨算法，提出见解）对于不同的测试数据，所用的时间也是不同的，比如对于快排来说，越有序的数列，时间越长。