大佬教程收集整理的这篇文章主要介绍了C++快速排序的分析与优化详解，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
相信学过数据结构与算法的朋友对于快速排序应该并不陌生，本文就以实例讲述了C++快速排序的分析与优化，对于C++算法的设计有很好的借鉴价值。具体分析如下：
一、快速排序的介绍
快速排序是一种排序算法，对包含n个数的输入数组，最坏的情况运行时间为Θ(n2)[Θ 读作theta]。虽然这个最坏情况的运行时间比较差，但快速排序通常是用于排序的最佳的实用选择。这是因为其平均情况下的性能相当好：期望的运行时间为 Θ(nlgn)，且Θ(nlgn)记号中隐含的常数因子很小。另外，它还能够进行就地排序，在虚拟内存环境中也能很好的工作。
和归并排序一样，快速排序也是基于分治法（divIDe and conquer）：
分解：数组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
for j=p+1 to r
do if A[j] <= x
then i = i+1
exchange(A[i],A[j])
exchange(A[p],A[i])
return i
QUICKSORT(A,r)
if p < r
then q = PARTITION(A,r)
QUICKSORT(A,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) 。
三、快排的优化
经过上面的分析可以知道，在输入有序或逆序时快速排序很慢，在其余情况则表现良好。如果输入本身已被排序，那么就糟了。那么我们如何确保对于所有输 入，它均能够获得较好的平均情况性能呢？前面的快速排序我们默认使用数组中第一个元素作为主元。假设随机选择数组中的元素作为主元，则快排的运行时间将不 依赖于输入序列的顺序。我们把随机选择主元的快速排序叫做Randomized Quicksort。
在随机化的快速排序中，我们不是始终选择第一个元素作为主元，而是从数组A[p…r]中随机选择一个元素，然后将其与第一个元素交换。由于主元元素是随机选择的，我们期望在平均情况下，对输入数组的划分能够比较对称。
伪代码如下：
RANDOMIZED-PARTITION(A,r)
i = RANDOM(p,r)
exchange(A[p],A[i])
return PARTITION(A,r)
RANDOMIZED-QUICKSORT(A,r)
if p < r
then q = RANDOMIZED-PARTITION(A,r)
RANDOMIZED-QUICKSORT(A,q-1)
RANDOMIZED-QUICKSORT(A,r)
我们对3万个元素的有序序列分别进行传统的快速排序 和 随机化的快速排序，并比较它们的运行时间：
/************************************************************************* > file name: QuickSort.cpp > Author: SongLee ************************************************************************/ #include<iostream> #include<cstdlib> // srand rand #include<ctime> // clock_t clock using namespace std; voID swap(int &a,int &b) { int tmp = a; a = b; b = tmp; } // 传统划分操作 int Partition(int a[],int low,int high) { int pivot = A[low]; int i = low; for(int j=low+1; j<=high; ++j) { if(A[j] <= pivot) { ++i; swap(A[i],A[j]); } } swap(A[i],A[low]); return i; } // 随机化划分操作，随机选择pivot int Partition_Random(int a[],int high) { srand(time(NulL)); int i = rand() % (high+1); swap(A[low],A[i]); return Partition(A,low,high); } // 传统快排 voID QuickSort(int a[],int high) { if(low < high) { int pos = Partition(A,high); QuickSort(A,pos-1); QuickSort(A,pos+1,high); } } // 随机化快速排序 voID QuickSort_Random(int a[],int high) { if(low < high) { int pos = Partition_Random(A,high); QuickSort_Random(A,pos-1); QuickSort_Random(A,high); } } int main() { clock_t t1,t2; // 初始化数组 int a[30000]; for(int i=0; i<30000; ++i) A[i] = i+1; t1 = clock(); QuickSort(A,30000-1); t1 = clock() - t1; cout << "Traditional quicksort took "<< t1 << " clicks(about " << ((float)t1)/CLOCKS_PER_SEC << " seconds)." << endl; t2 = clock(); QuickSort_Random(A,30000-1); t2 = clock() - t2; cout << "Randomized quicksort took "<< t2 << " clicks(about " << ((float)t2)/CLOCKS_PER_SEC << " seconds)." << endl; return 0; }
运行结果如下：
[songlee@localhost ~]$ ./QuickSort Traditional quicksort took 1210309 clicks(about 1.21031 seconds). Randomized quicksort took 457573 clicks(about 0.457573 seconds). [songlee@localhost ~]$ ./QuickSort Traditional quicksort took 1208038 clicks(about 1.20804 seconds). Randomized quicksort took 644950 clicks(about 0.64495 seconds).
从运行结果可以看出，对于有序的输入，随机化版本的快速排序的效率会高很多。
问题记录：
我们知道交换两个变量的值有以下三种方法：
int tmp = 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++快速排序的分析与优化详解所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。