一 点睛

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

合并排序每次都是从中间位置把问题一分为二，一直分解到不能再分时再进行合并操作。合并排序的划分很简单，但合并操作需要在辅助数组中完成，是一种异地排序的方法。合并排序分解容易、合并难，属于“先易后难”。而快速排序是原地排序，不需要辅助数组，但分解困难、合并容易，属于“先苦后甜”。

二 算法设计

快速排序是基于分治策略的，其算法思想如下。

1 分解

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

2 治理

对两个子序列进行快速排序。

3 合并

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

三 对基准元素的选取

• 一般有以下几种方法。
• 取第一个元素
• 取最后一个元素
• 取中间位置元素
• 取第一个元素，最后一个元素、中间位置的元素三者位置的中位数
• 取第一个元素和最后一个元素之间位置的随机数 k （low <= k <= high）,选第 k 个位置作为基准元素

四 图解

这里选取第一个元素作为基准。以说明快速排序的执行过程。

1 取当前待排序的第一个元素作为基准元素 pivot = r[low],i = low,j = high。

2 从右向左扫描，找小于或等于 pivot 的数，如果找到，则 r[i] 和 r[j] 交换，i++。

3 从左向右扫描，找大于 pivot 的数，如果找到，则 则 r[i] 和 r[j] 交换，j--。

4 重复第 2~3 步，直到 i 和 j 重合，将原数据分为两个子序列，左侧子序列都比 pivot 小，右侧序列都比 pivot 大。然后分别对这两个子序列进行快速排序。

这里以序列（30,24,5,58,18,36,12,42,39）为例，演示快速排序过程。

a 初始化

i = low ，j = high，pivot = r[low] = 30。

b 向左走

从数组的右边向左找，一直找小于或等于 pivot 的数，找到 r[j] = 12。

r[i] 和 r[j] 交换，i++。

c 向右走

从数组的左边向右找，一直找大于 pivot 的数，找到 r[i] = 58。

r[i] 和 r[j] 交换，j--。

d 向左走

从数组的右边向左找，一直找小于或等于 pivot 的数，找到 r[j] = 18。

r[i] 和 r[j] 交换，i++。

e 向右走

从数组的左边位置向右找，一直找比 pivot 大的数，此时 i = j，第一趟排序结束，返回 i 的位置，mid = i

此时以 mid 为界，将原序列分为两个子序列，左侧子序列都比 pivot 小，右侧子序列都比 pivot 大。然后分别对两个子序列（12,24,5,18）、（36、58、42、39）进行快速排序。

五 算法实现

快速排序实战_实践求真知-CSDN博客

https://blog.csdn.net/chengqiuming/article/details/114705971