文档介绍：快速排序算法三种情况下的运行时间比较
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位,)的