排序算法的时间性能比较.doc

《排序算法的时间性能比较.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、排序算法的时间性能比较一、问题描述给出一组实验来比较下列排序算法的时间性能：快速排序、堆排序、冒泡排序二、基本要求（1）时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。（2）实验数据应具有说服力，包括：规模范围要大（如从100到10000），数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出，如图、表等。（3）算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。（4）实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。（5）要给出实验的方案及其分析。三、工具/准备工

2、作MicrosoftVisualC++6.0软件。四、分析与实现1.快速选择排序这个是冒泡排序的一种改进，他的基本思想就是在当前无序区R【1….H】中任取一个数据元素的基准用此基准将当前无序区划分成左右二个较小的无序去区，R【1……i-1】和R【i+1…..H】，且左边的元素序子区中的数据元素均小于等于基数元素，右边的元素序子区中的数据元素均大于等于基数元素。直到所有无序子区中的数据元素均已排序为止。2.堆排序堆排序实质上就是具备有如下性质的完全二叉树：树中任一非子叶节点的关键字均大于等于其子孩子结点的关键字，它只要记录一个大小的辅助空间，每个待排序的记录只占有一个存储空间，一般记录数较小的。

3、但对基数较大的文件还是很有效的，因为运行时间主要是小号在建初始堆和调整建新堆时进行的反复的筛选上的。3.冒泡排序这种排序的比较基本思想就是二二比较待排序的数据元素的大小，发现二个数据元素的次序相反时候，就进行交换，知道没有反序的数据为止。冒泡排序是一种一次比较出最小或最大值，然后将其放置序列的最后一位置，再将剩下的从打一个位置开始到N-1的位置进行重复的操作。排序算法的时间空间复杂度排序方法最坏情况平均情况最好情况快速排序O（nlogn）O(n2)O(1)堆排序O(nlogn)O(nlogn)O(n)冒泡排序O(n2)O(nlogn)O(n)程序代码：#include#inc

4、lude#include#defineMAXSIZE50typedefintKeyType;#defineMAXNUM100typedefstruct{KeyTypeKey;}RedType;RedTypeR[MAXNUM];typedefstruct{RedTyper[MAXSIZE+1];intlength;}Sqlist;SqlistL,L0,L1,L2,L3,L4,L5,L6,L7;typedefSqlistHeadType;#defineRADIX10#defineMAX8#defineMAX_SPACE10000typedefintKeysTyp

5、e;typedefstruct{KeysTypeKeys[MAX];intnext;}SLCell;typedefstruct{SLCellrl[MAX_SPACE];intKeynum;intrecnum;}SLList;typedefintArrType[RADIX];intcompare[8];intchange[8];voidshuRu(SqlistL){inti=1,n;printf("请输入你输入的数据个数:");scanf("%d",&n);printf("请依次的输入各个数据值");L.length=n;for(;i<=L.length;i++){scanf("%d",

6、&L.r[i]);}}voidshuChu(SqlistL){inti=1;printf("该顺序存储中的数据元素为：");for(;i

7、e(low=pivotKey){--high;compare[4]++;}L.r[low]=L.r[high];change[4]++;compare[4]++;while(low