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

快速排序算法三种情况下的运行时间比较20116247汪敏快速排序算法是一种输入为n个数的数组，输出为n个数的有序数组的排序算法。虽然它的最坏情况的运行时间比较差，但是它的平均性能非常的好：平均的运行时间为，且记号中隐含的常数因子很小。因此，快速排序通常是用于排序的最佳实用选择。另外，它还能够进行就地排序，在虚存环境中也能很好的地工作。1 算法描述 快速排序算法是基于分治模式进行的。下面是对一个典型子数组排序的分治过程的三个步骤： 分解：数组被划分成两个(可能空的)子数组和，使得中的每个元素都小于等于，中的每个元素都大于等于。下标也在这个划分过程中进行计算。 解决：通过递归调用快速排序算法，对子数组和排序。 合并：因为两个子数组是就地排序的，将它们的合并不需要操作：整个数组已排序。22 核心操作及伪代码QUICKSORT(A,p,r)1 if pr2 then qPARTITION(A,p,r)3 QUICKSORT(A,p,q-1)4 QUICKSORT(A,q+1,r)递归地排序一个完整的数组，最初的调用是QUICKSORT(A,1,lengthA)。PARTITION(A,p,r)1 xAr2 ip-13 for jp to r-14 do if Ajx5 then ii+16 exchange Ai Aj7 exchange Ai+1 Ar8 return i+1PARTITION是快速排序算法的关键过程，它对子数组进行就地重排。3 算法性能及三种运行情况 快速排序的运行时间与输入数组和划分是否有规律有关，而后者又与选择了哪一个元素来进行划分有关。如果输入数组有序或是划分是有规律，那么本算法能达到最佳的运行时间；如果输入数组无序或是划分是无规律的，那么本算法会掉入最坏运行时间。具体地，我们将这些划分为以下的三种情况：最坏情况：1. 输入数组有序。2. Partition中取到的是数组中的最大值或是最小值。3. Partition过程中导致子数组和中的一个老是没有元素。在以上的三种最坏情况下算法的运行时间都为。本文选择第一种最坏情况编程测试。最好情况：在Partition过程中取到的始终将数组成比例划分：对等划分(1:1)，9:1划分。在这种情况下算法的运行时间都为。本文选择对等划分作为最好情况代表进行编程测试。平均(期望)情况：输入数组无序，在Partition过程的划分也无规律。在这种情况下算法的运行时间很接近最好情况的运行时间也是为。本文通过随机产生输入数组及将子数组的最后一位作为(标准值)进行编程测试。4 三种情况测试设置及C+代码实现测试环境编程语言：c+编译环境：Visual C+ 6.0测试电脑及处理器：Lenovo Win7 PC，Inter(R) Core(TM) i3-2330M CPU 2.20GHz 2.20 GHz数组大小：1000每种情况的总测试次数：1000平均情况：输入数组为数组元素为01的小数(保留小数点后6位)的大小为1000的数组，随机无规律产生。最坏情况：输入数组为数组元素为02的小数(保留小数点后6位，间隔为0.001)的大小为1000的有序数组。最好情况：输入数组为数组元素为02的小数(保留小数点后6位，间隔为0.001)的大小为1000的有序数组。我们选取对等划分作为最好情况测试代表，于是在Partition过程中，每次都取数组的中位数为标准值以做到对等划分。C+代码如下：函数声明部分，保存为Quicksort.h#ifndef QUICKSORT#define QUICKSORT#include #include #includeclass QuickSortprivate:const int arraySize;/数组大小float *array;/数组public:int flag;/三种情况的标志字QuickSort(int arraySize);/传递参数：数组大小QuickSort();/释放空间void Initial();/数组初始化int Partition(int first, int last);void Quicksort(int first, int last);void Sort();/第一次quicksort;#endif函数实现部分，保存为QuickSort.cpp#include QuickSort.hQuickSort:QuickSort(int Size):arraySize(Size)void QuickSort:Initial()array = new floatarraySize;switch (flag)case 0:/平均情况for(int i = 0; i arraySize; i+)arrayi = rand()/(float)(RAND_MAX);break;case 1:/最坏情况float base = rand()/(float)(RAND_MAX);for(int i = 0; i arraySize; i+)arrayi = base + (float)0.001*i;break;case 2:/最好情况float base = rand()/(float)(RAND_MAX);for(int i = 0; i arraySize; i+)arrayi = base + (float)0.001*i;int QuickSort:Partition(int first, int last)int i, j;float tempp;if(flag = 2)tempp = arraylong(first+(last-first)/2);arraylong(first+(last-first)/2) = arraylast;arraylast = tempp;j = first - 1;for(i = first; i last; i+)/Partition的精华思想，把last当做是标准if(arrayi arraylast)j +;float temp = arrayi;arrayi = arrayj;arrayj =temp;float temp = arraylast;arraylast = array+j;arrayj = temp;return j;void QuickSort:Quicksort(int first, int last)int pivot;if(first last)pivot = Partition(first, last);Quicksort(first, pivot - 1);Quicksort(pivot + 1, last);void QuickSort:Sort()Quicksort(0, arraySize - 1);QuickSort:QuickSort()delete array;主函数及测试代码部分，保存为test.cpp#include QuickSort.cppvoid main()int test_time = 1000;/测试次数int size = 1000;/数组大小clock_t start, finish;double totaltime = 0;QuickSort sort(size);for(int test_flag = 0;test_flag =2;test_flag +)for(int i = 1;i = test_time;i +)sort.flag = test_flag;sort.Initial();start = clock();/quicksort开始，计时开始sort.Sort();finish = clock();/quicksort结束，计时结束totaltime = (double)(finish - start) + totaltime;totaltime = totaltime / test_time;switch (test_flag)case 0:printf(QuickSort的average-case的running time为%fn,totaltime); break;case 1:printf(QuickSort的wo