1 / 7
文档名称:

快速排序算法三种情况下的运行时间比较.doc

格式:doc   大小:103KB   页数:7页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

快速排序算法三种情况下的运行时间比较.doc

上传人:mh900965 2018/1/4 文件大小:103 KB

下载得到文件列表

快速排序算法三种情况下的运行时间比较.doc

文档介绍

文档介绍:快速排序算法三种情况下的运行时间比较
20116247汪敏
快速排序算法是一种输入为n个数的数组,输出为n个数的有序数组的排序算法。虽然它的最坏情况的运行时间比较差,但是它的平均性能非常的好:平均的运行时间为,且记号中隐含的常数因子很小。因此,快速排序通常是用于排序的最佳实用选择。另外,它还能够进行就地排序,在虚存环境中也能很好的地工作。
算法描述
快速排序算法是基于分治模式进行的。下面是对一个典型子数组排序的分治过程的三个步骤:
分解:数组被划分成两个(可能空的)子数组和,使得中的每个元素都小于等于,中的每个元素都大于等于。下标也在这个划分过程中进行计算。
解决:通过递归调用快速排序算法,对子数组和排序。
合并:因为两个子数组是就地排序的,将它们的合并不需要操作:整个数组
已排序。[2]
核心操作及伪代码
QUICKSORT(A,p,r)
1 if p<r
2 then q←PARTITION(A,p,r)
3 QUICKSORT(A,p,q-1)
4 QUICKSORT(A,q+1,r)
递归地排序一个完整的数组,最初的调用是QUICKSORT(A,1,length[A])。
PARTITION(A,p,r)
x←A[r]
i←p-1
for j←p to r-1
do if A[j]≤x
then i←i+1
exchange A[i] A[j]
exchange A[i+1] A[r]
return i+1
PARTITION是快速排序算法的关键过程,它对子数组进行就地重排。
算法性能及三种运行情况
快速排序的运行时间与输入数组和划分是否有规律有关,而后者又与选择了哪一个元素来进行划分有关。如果输入数组有序或是划分是有规律,那么本算法能达到最佳的运行时间;如果输入数组无序或是划分是无规律的,那么本算法会掉入最坏运行时间。具体地,我们将这些划分为以下的三种情况:
最坏情况:
输入数组有序。
Partition中取到的是数组中的最大值或是最小值。
Partition过程中导致子数组和中的一个老是没有元素。
在以上的三种最坏情况下算法的运行时间都为。本文选择第一种最坏情况编程测试。
最好情况:
在Partition过程中取到的始终将数组成比例划分:对等划分(1:1),9:1划分。在这种情况下算法的运行时间都为。本文选择对等划分作为最好情况代表进行编程测试。
平均(期望)情况:
输入数组无序,在Partition过程的划分也无规律。在这种情况下算法的运行时间很接近最好情况的运行时间也是为。本文通过随机产生输入数组及将子数组的最后一位作为(标准值)进行编程测试。
三种情况测试设置及C++代码实现
测试环境
编程语言:c++
编译环境:Visual C++
测试电脑及处理器:Lenovo Win7 PC,Inter(R) Core(TM) i3-2330M CPU ***@ GHz
数组大小:1000
每种情况的总测试次数:1000
平均情况:
输入数组为数组元素为0~1的小数(保留小数点后6位)的大小为1000的数组,随机无规律产生。
最坏情况:
输入数组为数组元素为0~2的小数(保留小数点后6位,)的

最近更新

2025年度游艇租赁与水上赛事组织管理合同 9页

2025年度树苗种植与城市绿化提升工程合同 9页

2025年度智能家居产品赠与合同 10页

2025年度旅游景区装修拆除与景观重塑服务协议.. 10页

二次经营工作汇报[1] 53页

2025年度教育资源共享平台运营人员聘用合同 7页

2025年度手车过户车辆交易车辆交易税费减免协.. 8页

采购成本管理策略 46页

2025年度市政道路维修与城市地下空间利用合同.. 9页

2025年度家政护工雇用及服务质量监督协议 8页

2025年度安防产品研发合伙人股份合同 9页

2025年度城市轨道交通钢结构安全检测与维护服.. 9页

2025年度土地租赁与使用权出让合同 8页

2025年度商务办公区商用租房租赁及智能化服务.. 9页

2025年度司机职业发展规划与薪酬激励合同 8页

2025年度医院病房装饰装修工程设计合同书 10页

2025年度劳动合同补充协议书制作标准 8页

2025年度农业机械设备购销及培训合同 9页

第五十三届世乒赛中国男团夺冠的制胜因素分析.. 3页

2025年度住宿安全应急响应处理协议 8页

2025年度企业安全防护解决方案开发票协议 8页

智能家居设备购销合同简洁范本 6页

2025年度二手房买卖合同(无中介佣金) 8页

当代肖像画家—范勃绘画艺术解析 2页

旅游线路开发合作合同书 6页

阿里巴巴交易流程与注意事项 35页

新能源汽车融资租赁合同模板 6页

新版房屋装修施工合同范例大全 6页

川西孝泉—新场构造中三叠统雷口坡组地震沉积.. 21页

进一法和去尾法ppt 10页