以vector动态数组为例来详解快速排序算法

✅作者简介：C/C++领域新星创作者，为C++和java奋斗中 ✨个人社区：微凉秋意社区 🔥系列专栏：经典算法 📃推荐一款模拟面试、刷题神器👉注册免费刷题

🔥前言

今天还是算法的主题，分享快速排序的算法解析，并且使用vector容器实现，算是对知识的练习与巩固。这也是本专栏第七篇博文，以后遇到优化或者实用的算法我会继续写文分享在这一专栏，如果有朋友基础不牢或者初尝算法却不知道从何入手的都可以订阅观看《经典算法》专栏。

快速排序算法解析 一、掌握快排的算法流程

1. 算法思想如下：

通过一趟扫描将待排序的元素分割成独立的三个序列：第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置，因此需要再按此方法对第一个序列和第三个序列分别进行排序，整个排序过程可以递归进行，最终可使整个序列变成有序序列。

2. 其中的基准元素选择不唯一，可以采取以下五种方法：

• 取第一个元素
• 取最后一个元素
• 取位于中间位置的元素
• “三者取中的规则”
• 取位于low和high之间的随机数，用A[P]作为基准元素。即采用随机函数产生一个位于low和high之间的随机数P(low≤P≤high)，用A[P]作为基准，这相当于强迫R[low:high]中的元素是随机分布的

二、快排的代码实现与效果

C++源码：

#include
#include
#include
using namespace std;
//快排,分两步骤：分区和递归

//初始化动态数组
void getArray(vector& v)
{
	srand((unsigned int)time(NULL));
	int n = 0;
	cout  n;
	for (int i = 0; i