排序算法比较讲解.docxVIP

一． 排序算法比较 1. 问题描述 对直接插入排序,直接选择排序,冒泡排序,快速排序,堆排序五种排序算法进行比较. 要求: 1.被排序的对象由计算机随机生成,分别取长度为500,20000,1000000 2.算法中增加比较移动次数和比较次数的统计功能,并统计在排序同一组随机数时每种排序算法的运行时间,及占用内存情况. 3.对实验的结果进行比较 2.设计思路 这是一个算法性能评价程序,重点在于算法性能的评价上.实现某一功能可能有很多方法, 判断一个算法好坏的标准主要有时间复杂度和空间复杂度.在当今系统资源相对充足的计算机系统中,时间复杂度变成了头等问题. 对于每一个排序算法都应该有两个返回值:比较次数和移动次数.但在C语言中只能有一个函数返回值,故这里采用指针传递地址的方式通过形参的地址从而可以修改实参值.这样一来,在每个排序算法参数列表中,除了含被排序指针对象外,另外加两个整型变量指针,用于传递算法执行过程中的比较次数和移动次数. 取一定长度的对象,由计算机产生一定量的伪随机数后,主函数,调用各个排序函数,但由于排序对象也是指向一维数组的指针,在调用一次排序算法后,通过形参对指针的改变,被排序对象已经是有序的了.当再一次用其他排序算法后,有可能比较次数和移动次数达到最大或最小.无论是哪种情况都是不好的,这样一来,就失去了算法复杂度的比较意义了.为了避免这种情况的出现本程序采用在排序前新建一个数组,将保存随机数的数组复制到该数组,让排序算法对该数组进行排序.这样就不会改变原始对象的随机性. 在统计排序算法运行时间时采用新建两个time_t对象，排序开始前接收一次系统时间，排序结束后接收一次系统时间，二者的差值即为排序算法所运行的时间。 3.数据结构设计 本程序中考虑的内容是排序对象，排序的依据是关键字之间的大小比较。故在每个节点类型定义中，至少得包含关键字key这一项。被排序对象由一个个节点构成，一个排序对象包含一系列指向一串节点的指针，指针对象长度。具体说明如下： typedef struct { KeyType key;//关键字 int other;//数据 }DataType;//节点类型 typedef struct { DataType r[1000000]; int length;//排序对象的大小 }Sqlist;//排序对象类型 4.功能函数设计 （1）直接插入排序函数StrightInsertSort() 直接插入排序将待排序对象分为有序部分和无序部分，进行排序时逐次顺序提取无序部分的对象同有序部分的最后一个对象做比较，如果该对象大于有序部分最后一个对象，则将该对象插入到此位置，否则依次向左比较，直至找到插入位置。 （2） 直接选择排序函数Selectsort() 该排序算法首先在所有的n个带排序对象中找到最小的对象，将其与第1个对象做交换后，在后n-1个对象中继续找到最大对象，找到后将其与第2个对象交换。直至将所有的对象找到并插入适当位置即可。 (3)冒泡排序函数BubbleSort() 在每一趟冒泡排序中，依次比较相邻两个关键字的大小。若为反序，则交换。经过一趟冒泡后最大的关键字已经到达最后了。若按这种方法进行n-1趟冒泡，排序既能完成。 (4)堆排序函数Heapsort() 对排序的算法思想很简单，就是每次把关键字调整为堆，取出堆顶元素与最后一个元素交换，同时令堆的大小减一，把剩下的元素重新调整为堆，重复此过程，直到只剩下一个元素为止。 (5)快速排序函数 将带排序记录的第一个记录作为分区标准，将小于其的元素放在左边，将大于其的元素放在右边，中间放所选记录，为一趟快速排序。然后对两个子序列如此排序，直至所有记录有序。 5.程序代码 #include stdafx.h #includestdio.h #includestdlib.h #includetime.h #include windows.h #include psapi.h #include iostream using namespace std; #pragma once #pragma comment(lib,Psapi.lib) typedef int KeyType; typedef struct { KeyType key; int other; }DataType; typedef struct { DataType r[1000000]; int length; }Sqlist; void copy(Sqlist *a,Sqlist *b);//复制 int GetMemory() ;//得到系统开销状况 void SrandNum(Sqli