C++快速排序的分析与优化详解
相信学过数据结构与算法的朋友对于快速排序应该并不陌生,本文就以实例讲述了C++快速排序的分析与优化,对于C++算法的设计有很好的借鉴价值。具体分析如下:
一、快速排序的介绍
快速排序是一种排序算法,对包含n个数的输入数组,最坏的情况运行时间为Θ(n2)[Θ读作theta]。虽然这个最坏情况的运行时间比较差,但快速排序通常是用于排序的最佳的实用选择。这是因为其平均情况下的性能相当好:期望的运行时间为Θ(nlgn),且Θ(nlgn)记号中隐含的常数因子很小。另外,它还能够进行就地排序,在虚拟内存环境中也能很好的工作。
和归并排序一样,快速排序也是基于分治法(Divideandconquer):
分解:数组A[p..r]被划分成两个(可能为空)的子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于等于A[q],A[q+1..r]中的每个元素都大于等于A[q]。这样元素A[q]就位于其最终位置上了。
解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]排序。
合并:因为两个子数组是就地排序,不需要合并,整个数组已有序。
伪代码如下:
PARTITION(A,p,r) x=A[p] i=p forj=p+1tor doifA[j]<=x theni=i+1 exchange(A[i],A[j]) exchange(A[p],A[i]) returni QUICKSORT(A,p,r) ifp<r thenq=PARTITION(A,p,r) QUICKSORT(A,p,q-1) QUICKSORT(A,q+1,r)
二、性能分析
1、最坏情况
快速排序的最坏情况发生在当数组已经有序或者逆序排好的情况下。这样的话划分过程产生的两个区域中有一个没有元素,另一个包含n-1个元素。此时算法的运行时间可以递归地表示为:T(n)=T(n-1)+T(0)+Θ(n),递归式的解为T(n)=Θ(n^2)。可以看出,快速排序算法最坏情况运行时间并不比插入排序的更好。
2、最好情况
如果我们足够幸运,在每次划分操作中做到最平衡的划分,即将数组划分为n/2:n/2。此时得到的递归式为T(n)=2T(n/2)+Θ(n),根据主定理的情况二可得T(n)=Θ(nlgn)。
3、平均情况
假设一:快排中的划分点非常偏斜,比如每次都将数组划分为1/10:9/10的两个子区域,这种情况下运行时间是多少呢?运行时间递归式为T(n)=T(n/10)+T(9n/10)+Θ(n),使用递归树解得T(n)=Θ(nlgn)。可以看出,当划分点非常偏斜的时候,运行时间仍然是Θ(nlgn)。
假设二:Partition所产生的划分既有“好的”,也有“差的”,它们交替出现。这种平均情况下运行时间又是多少呢?这时的递归式为(G表示Good,B表示Bad):
G(n)=2B(n/2)+Θ(n)
B(n)=G(n-1)+Θ(n)
解:G(n)=2(G(n/2-1)+Θ(n/2))+Θ(n)=2G(n/2-1)+Θ(n)=Θ(nlgn)
可以看出,当好、差划分交替出现时,快排的运行时间就如全是好的划分一样,仍然是Θ(nlgn)。
三、快排的优化
经过上面的分析可以知道,在输入有序或逆序时快速排序很慢,在其余情况则表现良好。如果输入本身已被排序,那么就糟了。那么我们如何确保对于所有输入,它均能够获得较好的平均情况性能呢?前面的快速排序我们默认使用数组中第一个元素作为主元。假设随机选择数组中的元素作为主元,则快排的运行时间将不依赖于输入序列的顺序。我们把随机选择主元的快速排序叫做RandomizedQuicksort。
在随机化的快速排序中,我们不是始终选择第一个元素作为主元,而是从数组A[p…r]中随机选择一个元素,然后将其与第一个元素交换。由于主元元素是随机选择的,我们期望在平均情况下,对输入数组的划分能够比较对称。
伪代码如下:
RANDOMIZED-PARTITION(A,p,r) i=RANDOM(p,r) exchange(A[p],A[i]) returnPARTITION(A,p,r) RANDOMIZED-QUICKSORT(A,p,r) ifp<r thenq=RANDOMIZED-PARTITION(A,p,r) RANDOMIZED-QUICKSORT(A,p,q-1) RANDOMIZED-QUICKSORT(A,q+1,r)
我们对3万个元素的有序序列分别进行传统的快速排序和随机化的快速排序,并比较它们的运行时间:
/************************************************************************* >FileName:QuickSort.cpp >Author:SongLee ************************************************************************/ #include<iostream> #include<cstdlib>//srandrand #include<ctime>//clock_tclock usingnamespacestd; voidswap(int&a,int&b) { inttmp=a; a=b; b=tmp; } //传统划分操作 intPartition(intA[],intlow,inthigh) { intpivot=A[low]; inti=low; for(intj=low+1;j<=high;++j) { if(A[j]<=pivot) { ++i; swap(A[i],A[j]); } } swap(A[i],A[low]); returni; } //随机化划分操作,随机选择pivot intPartition_Random(intA[],intlow,inthigh) { srand(time(NULL)); inti=rand()%(high+1); swap(A[low],A[i]); returnPartition(A,low,high); } //传统快排 voidQuickSort(intA[],intlow,inthigh) { if(low<high) { intpos=Partition(A,low,high); QuickSort(A,low,pos-1); QuickSort(A,pos+1,high); } } //随机化快速排序 voidQuickSort_Random(intA[],intlow,inthigh) { if(low<high) { intpos=Partition_Random(A,low,high); QuickSort_Random(A,low,pos-1); QuickSort_Random(A,pos+1,high); } } intmain() { clock_tt1,t2; //初始化数组 intA[30000]; for(inti=0;i<30000;++i) A[i]=i+1; t1=clock(); QuickSort(A,0,30000-1); t1=clock()-t1; cout<<"Traditionalquicksorttook"<<t1<<"clicks(about"<<((float)t1)/CLOCKS_PER_SEC<<"seconds)."<<endl; t2=clock(); QuickSort_Random(A,0,30000-1); t2=clock()-t2; cout<<"Randomizedquicksorttook"<<t2<<"clicks(about"<<((float)t2)/CLOCKS_PER_SEC<<"seconds)."<<endl; return0; }
运行结果如下:
[songlee@localhost~]$./QuickSort Traditionalquicksorttook1210309clicks(about1.21031seconds). Randomizedquicksorttook457573clicks(about0.457573seconds). [songlee@localhost~]$./QuickSort Traditionalquicksorttook1208038clicks(about1.20804seconds). Randomizedquicksorttook644950clicks(about0.64495seconds).
从运行结果可以看出,对于有序的输入,随机化版本的快速排序的效率会高很多。
问题记录:
我们知道交换两个变量的值有以下三种方法:
inttmp=a;//方法一 a=b; b=tmp a=a+b;//方法二 b=a-b; a=a-b; a=a^b;//方法三 b=a^b; a=a^b;
但是你会发现在本程序中,如果swap函数使用后面两种方法会出错。由于方法二和方法三没有使用中间变量,它们交换值的原理是直接对变量的内存单元进行操作。如果两个变量对应的同一内存单元,则经过两次加减或异或操作,内存单元的值已经变为了0,因而不能实现变量值交换。所以当需要交换值的变量可能是同一变量时,必须使用第三变量实现交换,否则会对变量清零。
相关文章
- C++学习——c++逗号操作符说明(附加全部运算符优先级)
- EasyC++48,内部链接性和无链接性
- c++语言截取字符串,详解C++ string常用截取字符串方法
- c++算法之最长递增子序列(LIS)
- 快速排序算法——C/C++
- 图解快速排序(C++实现)
- c++获取子类窗口句柄位置_C++中各种获取窗口句柄的方法「建议收藏」
- c++中如何定义常量_电脑基础知识教程自学
- 各种常用排序算法(C/C++,Java)动态显示
- C++项目贪吃蛇游戏笔记-C语言版
- C++构造函数的作用_c++什么是构造函数
- 链表排序总结(全)(C++)[通俗易懂]
- 简单的Python调用C++程序
- C++ 不知算法系列之从希尔、归并排序算法中的分治哲学聊起
- C++ STL 标准模板库(排序/集合/适配器)算法
- C/C++ Qt 常用数据结构
- 从C和C++内存管理来谈谈JVM的垃圾回收算法设计-下
- c++stl
- 基于c/c++的希尔排序与插入排序对比
- C/C++/Java 程序计时功能函数详解编程语言
- C++String 类完整源代码详解编程语言
- C++ discrete_distribution离散分布随机数函数用法详解
- C++类型转换运算符(无师自通)
- 选择排序(C++)算法(超详细)
- C++快速排序(递归)算法详解
- 用C操作MySQL实现数据写入(c++ mysql 写入)
- C++的sstream标准库详细介绍
- C++explicit关键字的应用方法详细讲解