排序算法——快速排序的图解、代码实现以及时间复杂度分析_median-of-three partitioning快速排序时间复杂度

快速排序

在C++的泛型排序中，拷贝对象需要很大的开销，而比较对象常常是相对省时的（编译器的自动优化）。在这种情况下，如果我们能够使用更少的数据移动，那么有理由让一个算法多使用一些比较。而快速排序（Quicksort）满足了这种特点，实际上C++中通常所使用的排序例程就是使用的快速排序。
快速排序也是一种分治的递归算法。它的平均运行时间是O(NlogN)，最坏情形性能为O(N²)。

经典快速排序

将数组S排序的基本算法由下列简单的四步组成：

1. 如果S中元素个数是0或1，则返回
2. 取S中的任一元素V，称之为枢纽元（pivot）
3. 将S-{V}（S中的其他元素）划分成两个不相交的集合：S1={小于V的元素}，S2={大于V的元素}。
4. 返回{quicksort(S1)后跟V，继而返回quicksort(S2)}

实现第2步和第3步有很多方法，下面介绍的方法是大量分析和实验的结果。

一、选取枢纽元

虽然上面说随机选取一个元素作为枢纽元，但是有些选择显然优于其他选择。

一种错误的方法

通常的、无知的选择是将第一个元素用作枢纽元。如果输入是随机的，那么这是可以接受的，而如果输入是预排序的或是反序的，那么所有的元素不是都被划入S1就是都被划入S2，这将花费二次时间。而且，预排序的输入（或具有一大段预排序数据）是相当常见的。因此，使用第一个元素作为枢纽元是绝对可怕的坏主意。

一种安全的做法

一种安全的方法是随机选取枢纽元。一般来说这种策略非常安全，因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面，随机数的生成一般开销很大，根本减少不了算法其余部分的平均运行时间。

三数中值分割法（Median-of-Three Partitioning）

枢纽元的最好选择是数组的中值。不幸的是，这很难算出并且会明显减慢快速排序的速度。一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的坏情形，并且实际减少了14%的比较次数。

二、分割策略

暂时假设所有的元素互异。一种高效的做法是，将枢纽元与最后一个元素交换使得枢纽元脱离分割，i从第一个元素开始而j从倒数第二个元素开始。
在分割阶段要做的就是把所有小元素移到数组的左边而把所有的大元素移到数组的右边，当然，小和大是相对于枢纽元而言的。
i右移到大于枢纽元的位置，j左移到小于枢纽元的位置，如果i < j ，那么交换i、j对应的元素，其效果是把一个大元素推向右边而把小元素推向左边。以此类推，知道i=j。分割的最后一步是将枢纽元与i所指向的元素交换。

三、图解演示

以序列8，1，4，9，6，3，5，2，7，0为例，最左边元素为8，右边元素是0，中心位置元素是6，于是选定枢纽元pivot=6。
一轮快速排序