数据结构课程设计报告 各种排序算法性能比较.doc

数据结构（C语言）课程设计报告 各种排序算法性能比较课程设计报告课程设计题目：各种排序算法性能比较学生姓名:学 号：专 业：信息管理与信息系统班 级：指导教师： 2012年 06 月 23 日目录CONTENTS一、 课程设计目的2二、课程设计题目概述2三、数据定义2四、各种排序的基本原理及时间复杂度分析3五、程序流程图6六、程序源代码6七、程序运行与测试15八、实验体会九、参考文献一、 课程设计目的课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。二、课程设计题目概述排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果排序中依据的不同原则对内部排序方法进行分类，则大致可分为直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序、堆排序等六类排序算法。本实验是对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序、堆排序这几种内部排序算法进行比较，用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。最后用图表数据汇总，以便对这些内部排序算法进行性能分析。三、数据定义输入数据：由于大多数排序算法的时间开销主要是关键字之间的比较和记录的移动，算法的执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。所以对于输入数据，我们采用由用户输入记录的个数（以关键字的数目分别为20，100，500为例），测试数据由随机数产生器生成。输出数据：产生的随机数分别用直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序这些排序方法进行排序，输出关键字的比较次数和移动次数。四、各种排序的基本原理及时间复杂度分析1、直接插入排序（InsertSort）1.1、基本原理：假设待排序的n个记录R0，R1，Rn顺序存放在数组中，直接插入法在插入记录Ri(i=1，2，n-1)时，记录被划分为两个区间R0,Ri-1和Ri+1,Rn-1,其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码Ki与Ki-1Ki-2，K0依次比较，找出应该插入的位置，将记录Ri插，然后将剩下的i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i-1趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。1.2、时间复杂度分析：直接插入排序算法必须进行n-1趟。最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是O(n)。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为O(n2)。2、直接选择排序（SelectSort）2.1、基本原理：待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。第一趟第n个记录中找出关键码最小的记录与第n个记录交换；第二趟，从第二个记录开始的，2 -1个记录中再选出关键码最小的记录与第二个记录交换；如此，第 i 趟，则从第i个记录开始的 n - i + l个记录中选出关键码最小的记录与第 i 个记录交换，直到所有记录排好序。2.2、时间复杂度分析：该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为O(n2)。3、冒泡排序（BubbleSort）3.1、基本原理在每一趟冒泡排序中，依次比较相邻的两个关键字大小，若为反序咋交换。经过一趟起泡后，关键词大的必须移到最后。按照这种方式进行第一趟在序列（I0In-1）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到In-1中，下一趟只需在子序列（I0In-2）中进行；如果在某一趟排序中未交换元素，则不再进行下一趟排序。将被排序的记录数组J1 n垂直排列，每个记录Ji看作是重量为Ji.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止，最后可完成。3.2、时间复杂度分析当原始数据正向有序时，冒泡排序出现最好情况。此时，只需进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是O(n)。当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进行n-1趟排序，第i趟作(n-i)次关键字间的比较，并且需执行(n-i)次元素交换，所以，比较次数为：因此,最坏情况下的时间复杂度为O(n2)4、Shell排序（ShellSort）4.1、基本原理Shell排序又称缩小增量排序,Shell排序法是以创建者Donald Shell的名字命名的.Shell排序法是对相邻指定距离(称为间隔)的元素进行比较,已知到使用当前间隔进行比较的元素都按顺序排序为止.Shell把间隔缩小一半,然后继续处理,当间隔最终变为1,并且不再出现变化时,Shell排序也就完成了其处理过程.先取一个整数d1n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，先在各组内排序；然后去d2d1重复上诉分组和排序工作；直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入，直到dt=1，即所有记录放在一组中为止。4.2、时间复杂度分析希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。所以希尔排序是不稳定的，其时间复杂度为o(n2)。5、快速排序（QuickSort）5.1基本原理首先我们选择一个中间值 middle （程序中我们可使用数组中间值），把比中问值小的放在其左边，比中问值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架。在待排序的个记录中任意取一个记录（通常取第一个记录）为区分标准，把所有小于该排序的记录移到左边，把所有大于该排序码的记录移到右边，中级放所选记录，为一趟快速排序。然后对前后两个子序列分别重新上述过程，直到所有记录都排好序。对任意给定的序列中某个元素，经过一趟排序后，将原序列分割成两个子序列(Rp(0),Rp(1),Rp(s-1)和(Rp(s+1),Rp(s+2),Rp(n-1)，其中前一个子序列中的所有元素的关键词均小于或等于该元素的关键词值Kp(s)，后一个子序列中元素的关键词均大于或等于Kp(s)。称该元素Rp(s)为分割元素，子序列(Rp(0),Rp(1),Rp(s-1)为其低端序列，(Rp(0),Rp(1),Rp(s-1)为其高端序列。很明显，以后只需对低端和高端序列分别进行快速排序，直到子序列为空或只有一个元素时结束，最后得到有序序列。总之，每趟使表的第一个元素放在适当位置，将表两分，再对子表进行同样的递归划分，直至划分的子表长度为1。5.2、时间复杂度分析如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O(nlog2n)；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时间复杂度为O(n2)。如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为O(nlog2n)。6、堆排序（Heapsort）6.1、基本原理 堆排序思想很简单，就是每次把关键词调整为堆，取出堆顶元素与堆中最后一个元素交换，同时令堆的大小减一，把剩余的一些元素重新调整为堆，重复此过程，知道堆中只剩下一个元素，n个关键字序列K1,K2,K3, 称为堆，当且仅当该序列满足如下性质（简称为堆性质）：（1）Ki=K2i且Ki=K2i+1或（2）Ki=K2i+1.。若将此序列所存储的向量R1n看作是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中的最大者，称为大根堆。注意：堆中任一子树亦是堆。以上讨论的实际上是二叉堆，类似的可以定义K叉堆6.2时间复杂度分析堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度O(nlogn)。五、程序流程图主程序产生1组随机数起泡排序Shell排序快速排序直接选择排序记录关键字的比较次数和移动次数将随机数保存在数组中循环20次输出关键字的比较次数、移动次数的平均值直接插入排序 图5.1 程序流程图六、程序源代码#include#includetypedef structint key; /*关键字*/RecordNode; /*排序节点的类型*/typedef structRecordNode *record;int n; /*排序对象的大小*/SortObject; /*排序节点的类型*/void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)int i,j;RecordNode temp; SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL)printf(OverFollow!);getchar();exit(1);for(i=0;in;i+)/* 复制数组*/pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=1;in;i+) temp=pvector-recordi; (*exchange)+; j=i-1; while(temp.keyrecordj.key)&(j=0) (*compare)+; (*exchange)+; pvector-recordj+1=pvector-recordj; j-; if(j!=(i-1) pvector-recordj+1=temp; (*exchange)+; free(pvector);void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange) int i,j,k; RecordNode temp; SortObject *pvector; if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf(OverFollow!);getchar();exit(1); for(i=0;in;i+)/*复制数组*/pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) (*compare)+; if(pvector-recordj.keyrecordk.key)k=j; if(k!=i) temp=pvector-recordi; pvector-recordi=pvector-recordk; pvector-recordk=temp; ( *exchange)+=3; free(pvector);void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange) int i,j,noswap; RecordNode temp; SortObject *pvector; if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf(OverFollow!); getchar(); exit(1); for(i=0;in;i+)/* 复制数组*/ pvector-recordi=p-recordi; pvector-n=p-n; *compare=0; *exchange=0; for(i=0;in-1;i+) noswap=1; for(j=0;jn-i-1;j+) (*compare)+; if(pvector-recordj+1.keyrecordj.key) temp=pvector-recordj; pvector-recordj=pvector-recordj+1; pvector-recordj+1=temp; (*exchange)+=3; noswap=0; if(noswap) break; free(pvector);void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange) int i,j,increment; RecordNode temp; SortObject *pvector; if(pvector=(SortObject*)malloc(sizeof(SortObject)=NULL) printf(OverFollow!); getchar(); exit(1); for(i=0;in;i+)/* 复制数组*/pvector-recordi=p-recordi; pvector-n=p-n; *compare=0; *exchange=0; for(increment=d;increment0;increment/=2) for(i=increment;in;i+) temp=pvector-recordi; (*exchange)+; j=i-increment; while(j=0&temp.keyrecordj.key) (*compare)+; pvector-recordj+increment=pvector-recordj; (*exchange)+; j-=increment; pvector-recordj+increment=temp; (*exchange)+; free(pvector);Void SiftHeap(SortObject *pvector,int size,int p,unsigned long *compare,unsigned long *exchange) RecordNode temp; int i,child; temp=pvector-recordp; (*exchange)+; i=p; child=2*i+1; while(childsize) if(childrecordchild.keyrecordchild+1.key) (*compare) +; child+; if(temp.keyrecordchild.key) (*compare)+; pvector-recordi=pvector-recordchild;(*exchange)+; i=child; child=2*i+1;else break; pvector-recordi=temp; (*exchange)+;void HeapSort(SortObject *p,unsigned long *compare,unsigned long *exchange) int i,n; RecordNode temp; SortObject *pvector; if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf(OverFollow!); getchar(); exit(1); for(i=0;in;i+) pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;n=pvector-n;for(i=n/2-1;i=0;i-)SiftHeap(pvector,n,i,compare,exchange); temp=pvector-record0; pvector-record0=pvector-recordi; pvector-recordi=temp; (*exchange)+=3; SiftHeap(pvector,i,0,compare,exchange);free(pvector);void QuickSort(SortObject *pvector,int left,int right,unsigned long*compare,unsigned long *exchange) int i,j; RecordNode temp; if(left=right)return; i=left; j=right; temp=pvector-recordi; (*exchange)+; while(i!=j) while(pvector-recordj.key=temp.key)&(ji) (*compare)+; j-; if(irecordi+=pvector-recordj;(*exchange)+; while(pvector-recordi.keyi) (*compare)+;i+; if(irecordj-=pvector-recordi;(*exchange)+; pvector-recordi=temp; (*exchange)+; QuickSort(pvector,left,i-1,compare,exchange); QuickSort(pvector,i+1,right,compare,exchange);void SortMethod(void) int i,j; unsigned long num312=0; SortObject *pvector=(SortObject *)malloc(sizeof(SortObject); int random; randomize(); for(j=0;j3;j+) for(i=0;irecordi.key=random(5000); pvector-n=MAXSORTNUMj; InsertSort(pvector,&numj0,&numj1); SelectSort(pvector,&numj2,&numj3); BubbleSort(pvector,&numj4,&numj5); ShellSort(pvector,4,&numj6,&numj7); Heapsort(pvector,&numj8,&numj9);QuickSort(pvector,0,MAXSORTNUMj-1,&numj10,&numj11); printf(nSort Method Compare As Follows:); for(j=0;j%-7ld Exchanged-%-7ldn,numj0,numj1);printf(2.SelectSort Method:Compared-%-7ld Exchanged-%-7ldn,numj2,numj3);p