快速排序算法C++实现（超详细解析！！！！）

目录

一、前言

（1）分治算法

（2）分治算法解题方法

    1.分解：

    2.治理：

    3.合并：

二、快速排序

1.问题分析

2.算法设计

    （1）分解：

    （2）治理 ：

    （3）合并：

    （4）基准元素的选取：

3.算法分析

三、AC代码

 四、共勉

---

一、前言

（1）分治算法

    快速排序，其实是一种分治算法，那么在了解快速排序之前，我们先来看看什么是分治算法。在算法设计中，我们引入分而治之的策略，称为分治算法，其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题，分而治之。

（2）分治算法解题方法

    1.分解：

    将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。

    2.治理：

    求解各个子问题。由于各个子问题与原问题形式相同，只是规模较小而已，而当子问题划分得足够小时，就可以用简单的方法解决。

    3.合并：

    按原问题的要求，将子问题的解逐层合并构成原问题的解。

二、快速排序

1.问题分析

    快速排序是比较快的排序方法。它的基本思想是通过一组排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据小，然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此使所有数据变成有序序列。

2.算法设计

    （1）分解：

    先从数列中取出一个元素作为基准元素。一基准元素为标准，将问题分解为两个子序列，使小于或者等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。

    （2）治理 ：

    对两个子序列进行快速排序（递归快速排序）。

    （3）合并：

    将排好的两个子序列合并在一起，得到原问题的解。

    （4）基准元素的选取：

    ①：取第一个元素。(通常选取第一个元素)

    ②：取最后一个元素

    ③：取中间位置的元素

    ④：取第一个、最后一个、中间位置元素三者之中位数

    ⑤：取第一个和最后一个之间位置的随机数 k (low