1、一 排序算法比较1. 问题描述对直接插入排序,直接选择排序, 冒泡排序,快速排序,堆排序五种排序算法进行比较 .要求: 1.被排序的对象由计算机随机生成,分别取长度为 500,20000,10000002.算法中增加比较移动次数和比较次数的统计功能,并统计在排序同一组随机数时每种排序算法的运行时间,及占用内存情况.3.对实验的结果进行比较2.设计思路这是一个算法性能评价程序,重点在于算法性能的评价上.实现某一功能可能有很多方法,判断一个算法好坏的标准主要有时间复杂度和空间复杂度.在当今系统资源相对充足的计算机系统中,时间复杂度变成了头等问题.对于每一个排序算法都应该有两个返回值:比较次数和移动
2、次数.但在 C 语言中只能有一个函数返回值,故这里采用指针传递地址的方式通过形参的地址从而可以修改实参值.这样一来,在每个排序算法参数列表中, 除了含被排序指针对象外,另外加两个整型变量指针, 用于传递算法执行过程中的比较次数和移动次数.取一定长度的对象,由计算机产生一定量的伪随机数后, 主函数,调用各个排序函数, 但由于排序对象也是指向一维数组的指针,在调用一次排序算法后,通过形参对指针的改变,被排序对象已经是有序的了.当再一次用其他排序算法后,有可能比较次数和移动次数达到最大或最小. 无论是哪种情况都是不好的,这样一来, 就失去了算法复杂度的比较意义了 .为了避免这种情况的出现本程序采用在
3、排序前新建一个数组,将保存随机数的数组复制到该数组,让排序算法对该数组进行排序.这样就不会改变原始对象的随机性.在统计排序算法运行时间时采用新建两个time_t对象，排序开始前接收一次系统时间，排序结束后接收一次系统时间，二者的差值即为排序算法所运行的时间。3.数据结构设计本程序中考虑的内容是排序对象，排序的依据是关键字之间的大小比较。故在每个节点类型定义中，至少得包含关键字 key 这一项。被排序对象由一个个节点构成，一个排序对象包含一系列指向一串节点的指针，指针对象长度。具体说明如下：typedef structKeyType key;/关键字int other;/数据DataType;/
4、节点类型typedef structDataType r1000000;int length;/排序对象的大小Sqlist;/排序对象类型4.功能函数设计（1）直接插入排序函数StrightInsertSort()直接插入排序将待排序对象分为有序部分和无序部分，进行排序时逐次顺序提取无序部分的对象同有序部分的最后一个对象做比较，如果该对象大于有序部分最后一个对象，则将该对象插入到此位置，否则依次向左比较，直至找到插入位置。（2） 直接选择排序函数Selectsort()该排序算法首先在所有的n个带排序对象中找到最小的对象，将其与第1个对象做交换后，在后n-1个对象中继续找到最大对象，找到后将其
5、与第2个对象交换。直至将所有的对象找到并插入适当位置即可。(3)冒泡排序函数BubbleSort()在每一趟冒泡排序中，依次比较相邻两个关键字的大小。若为反序，则交换。经过一趟冒泡后最大的关键字已经到达最后了。若按这种方法进行n-1趟冒泡，排序既能完成。(4)堆排序函数Heapsort()对排序的算法思想很简单，就是每次把关键字调整为堆，取出堆顶元素与最后一个元素交换，同时令堆的大小减一，把剩下的元素重新调整为堆，重复此过程，直到只剩下一个元素为止。(5)快速排序函数将带排序记录的第一个记录作为分区标准，将小于其的元素放在左边，将大于其的元素放在右边，中间放所选记录，为一趟快速排序。然后对两个
6、子序列如此排序，直至所有记录有序。5.程序代码#include “stdafx.h“#include“stdio.h“#include“stdlib.h“#include“time.h“#include “windows.h“#include “psapi.h“#include “iostream“using namespace std;#pragma once#pragma comment(lib,“Psapi.lib“)typedef int KeyType;typedef structKeyType key;int other;DataType;typedef structDataTyp
7、e r1000000;int length;Sqlist;void copy(Sqlist *a,Sqlist *b);/复制int GetMemory() ;/得到系统开销状况void SrandNum(Sqlist *s,int num);/生成随机数void StrightInsertSort(Sqlist *s,long *compare,long *exchange);/直接插入排序void BubbleSort(Sqlist *s,long *compare,long *exchange);/冒泡排序void Quicksort(Sqlist *s,int low,int high
8、,long *compare,long *exchange);/递归形式的快速排序void Selectsort(Sqlist *s,long *compare,long *exchange);/直接选择排序void Heapsort(Sqlist *s,long *compare,long *exchange);/堆排序void out(Sqlist *s);/输出排序结果int _tmain(int argc, _TCHAR* argv)/主函数int i,num;long *compare,*exchange;/记录比较及交换次数compare=(long *)malloc(sizeof
9、(long);/开辟空间exchange=(long *)malloc(sizeof(long);Sqlist *s,*tmp;s=(Sqlist *)malloc(sizeof(Sqlist);tmp=(Sqlist *)malloc(sizeof(Sqlist);printf(“请输入生成的随机数的数目：n“);cinnum;SrandNum(s, num);/生成随机数time_t start,end;/start，end分别记录开始及结束时系统时间/printf(“n生成的随机数如下：n“);/out(s);printf(“直接插入排序情况：n“); /直接插入排序copy(s,tmp
10、);*compare=*exchange=0;start=clock();StrightInsertSort(tmp,compare,exchange);end=clock();printf(“ 排序运行时间%dmsn“,end-start);printf(“比较次数：%d 交换次数：%d“,*compare,*exchange);/printf(“n排序结果如下n“);/out(tmp);printf(“nn冒泡排序情况：n“); /冒泡排序copy(s,tmp);*compare=*exchange=0;start=clock();BubbleSort(tmp,compare,exchan
11、ge);end=clock();printf(“ 排序运行时间%dmsn“,end-start);printf(“比较次数：%d 交换次数：%d“,*compare,*exchange);/printf(“n排序结果如下n“);/out(tmp);printf(“nn快速排序情况：n“); /快速排序copy(s,tmp);*compare=*exchange=0;start=clock();Quicksort(tmp,1,tmp-length,compare,exchange);end=clock();printf(“ 排序运行时间%dmsn“,end-start);printf(“比较次数
12、：%d 交换次数：%d“,*compare,*exchange);/printf(“n排序结果如下n“);/out(tmp);printf(“nn直接选择排序情况：n“); /直接选择排序copy(s,tmp);*compare=*exchange=0;start=clock();Selectsort(tmp,compare,exchange);end=clock();printf(“ 排序运行时间%dmsn“,end-start);printf(“比较次数：%d 交换次数：%d“,*compare,*exchange);/printf(“n排序结果如下n“);/out(tmp);printf
13、(“nn堆排序情况：n“); /堆排序copy(s,tmp);*compare=*exchange=0;start=clock();Heapsort(tmp,compare,exchange);end=clock();printf(“ 排序运行时间%dmsn“,end-start);printf(“比较次数：%d 交换次数：%d“,*compare,*exchange);/printf(“n排序结果如下n“);/out(tmp);return 0;void copy(Sqlist *a,Sqlist *b)/将a复制到b中int i;for(i=1;ilength ;i+)b-r i.key=
14、a-r i.key ;b-length =a-length ;void SrandNum(Sqlist *s,int num) /生成num个随机数保存到s中int i;time_t t;srand(unsigned)time( /新建时间种子for(i=1;iri.key=rand(); /生成随机数s-length=num;void StrightInsertSort(Sqlist *s,long *compare,long *exchange)/直接插入排序int i,j;*compare=*exchange=0;for(i=2;ilength ;i+)s-r 0=s-r i; /复制到
15、前哨站(*compare)+;(*exchange)+;j=i-1;while(s-r 0.key r j.key )/当前数据的关键字大于前哨站的关键字，则后移(*compare)+;(*exchange)+;s-r j+1=s-r j;j-; s-r j+1=s-r 0; /插入到正确的位置(*exchange)+;void BubbleSort(Sqlist *s,long *compare,long *exchange)/冒泡排序int i,j;for(i=1;ilength-1;i+)for(j=2;jlength-i;j+) /进行n-1趟冒泡if(s-rj.keyrj-1.key
16、)s-r0.key=s-rj.key;s-rj.key=s-rj-1.key;s-rj-1.key=s-r0.key;(*exchange)+=3;(*compare)+;int Quicksort1(Sqlist *s,int low,int high,long *compare,long *exchange) /一趟快速排序/交换顺序表s中的记录，使轴值到达其最终位置，并返回轴值的位置/此时，在轴值之前的数字都小于它，在轴值后面的数字都大于它int pivotkey;s-r0=s-rlow; /以子表的第一个记录作为轴值支点pivotkey=s-rlow.key; /取轴值的关键字(*exchange)+=2;while(lowr high.key=pivotkey)high-;(*compare)+=2;
