算法与数据结构：手动计算快速排序后结果

快速排序定义

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

• 1．先从数列中取出一个数作为基准数。
• 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 3．再对左右区间重复第二步，直到各区间只有一个数。

——来自《菜鸟教程》

快速排序的具体过程就不介绍了，网上有太多的教程了。

此处的教程仅为算法与数据结构中快速排序的手动计算每一轮的结果提供简便方法。

以下介绍的为个人推论，如有误，请指正。

Q：对于一个序列，我们要将其按照升序排列：

我们将第一个数设为基准数，使用红色标注。

第一轮排序

我们将所有小于基准数的数标为橙色，所有大于(包括等于)基准数的数标为紫色。

之后标出指向箭头，可以先标橙色元素，也可以先标紫色元素。（标注顺序不影响结果）

标箭头按照以下规律进行：

• 首先定义基准数和大于(包括等于)基准数的数为大数，小于基准数的数为小数。
• 每个数都有一个指出的箭头，和一个指入的箭头。只有基准数没有指出的箭头。
• 所有数的箭头不相交。
• 小于基准数的数从右往左开始画箭头，箭头从最左侧大数开始向右指，直到该位置左侧没有大数可以指为止。
• 大于(包括等于)基准数的数从左往右开始画箭头，箭头从最右侧小数开始向左指，直到该位置右侧没有小数可以指为止。

因此箭头指向如下：

此时，如上图由于 42位置没有指入箭头，只有指出箭头，因此将基准数放到 42所在位置。

指完箭头之后，将箭头尾部的数替换到箭头指向的位置。

因此第一轮排序的结果如下：

可以看到基准数左侧均小于基准数，右侧均大于基准数。

第二轮排序

此时我们使用 48作为基准数。

则排序箭头如下：

结果如下：

之后的排序依旧按照如上规律进行，后续不在赘述。