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, p, r) if p < r then q = 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) 。
三、快排的优化
经过上面的分析可以知道,在输入有序或逆序时快速排序很慢,在其余情况则表现良好。如果输入本身已被排序,那么就糟了。那么我们如何确保对于所有输 入,它均能够获得较好的平均情况性能呢?前面的快速排序我们默认使用数组中第一个元素作为主元。假设随机选择数组中的元素作为主元,则快排的运行时间将不 依赖于输入序列的顺序。我们把随机选择主元的快速排序叫做Randomized Quicksort。
在随机化的快速排序中,我们不是始终选择第一个元素作为主元,而是从数组A[p…r]中随机选择一个元素,然后将其与第一个元素交换。由于主元元素是随机选择的,我们期望在平均情况下,对输入数组的划分能够比较对称。
伪代码如下:
RANDOMIZED-PARTITION(A, p, r) i = RANDOM(p, r) exchange(A[p], A[i]) return PARTITION(A, p, r) RANDOMIZED-QUICKSORT(A, p, r) if p < r then q = RANDOMIZED-PARTITION(A, p, r) RANDOMIZED-QUICKSORT(A, p, q-1) RANDOMIZED-QUICKSORT(A, q+1, 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 low, 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 low, int high) { if(low < high) { int pos = Partition(A, low, high); QuickSort(A, low, pos-1); QuickSort(A, pos+1, high); } } // 随机化快速排序 void QuickSort_Random(int A[], int low, int high) { if(low < high) { int pos = Partition_Random(A, low, high); QuickSort_Random(A, low, pos-1); QuickSort_Random(A, pos+1, 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, 0, 30000-1); t1 = clock() - t1; cout << "Traditional quicksort took "<< t1 << " clicks(about " << ((float)t1)/CLOCKS_PER_SEC << " seconds)." << endl; t2 = clock(); QuickSort_Random(A, 0, 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,因而不能实现变量值交换。所以当需要交换值的变量可能是同一变量时,必须使用第三变量实现交换,否则会对变量清零。
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 关于mysql效率优化一般通过以下两种方式定位执行效率较低的sql语句。通过慢查询日志定位那些执行效率较低的 SQL 语句,用 --log-slow-queries[=file_name] 选项启动时, mysqld 会 写一个包含所有执行时间超过 long_quer...2015-11-08
- 过了这么久,discuz论坛的问题还是困扰着很多网友,其实从各论坛里看到的问题总结出来,很关键的一点都是因为没有将数据表引擎转成InnoDB导致的,discuz在并发稍微高一点的环境下就表现的非常糟糕,产生大量的锁等待,这时候如果...2015-11-24
- java开发的Android应用,性能一直是一个大问题,,或许是Java语言本身比较消耗内存。本文我们来谈谈Android 性能优化之MemoryFile文件读写。 Android匿名共享内存对外A...2016-09-20
- MySQL是一个功能强大的开源数据库。随着越来越多的数据库驱动的应用程序,人们一直在推动MySQL发展到它的极限。这里是101条调节和优化 MySQL安装的技巧。一些技巧是针对特定的安装环境的,但这些思路是通用的。我已经把...2013-09-11
- 这篇文章主要介绍了Angular性能优化之第三方组件和懒加载技术,对性能优化感兴趣的同学,可以参考下...2021-05-11
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 本文给大家介绍的是C#程序优化的小技巧,通过此方法可以有效的降低CPU的占用率,十分的简单实用,有需要的小伙伴可以参考下。...2020-06-25
- 这篇文章主要介绍了JavaScript提高网站性能优化的建议(二)的相关资料,需要的朋友可以参考下...2016-07-29
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29