1.4排序——快排：它到底快不快

快排是一种使用广泛的排序，它比merge需要的空间更小，而且改进过的快排速度很快，平均O(nlgn)。快排也用到了递归的思想，所以我才说递归很重要的嘛。

我们大概看一下快排的基本过程：选择一个数，把小于它的放左边，不小于它的放右边。没了。那么很显然，这个算法的特点和难点就是“怎么选出一个合适的点”和“怎么实现‘放’”。选择肯定是超重要的，还记得上一节的“递归树”吗，如果采用“二路归并”，在这里就是分为2个序列，那么最好是把分开的点选在中间，因为树高是通过最长路径来计算的。

另一个问题就是怎么实现这个“通过一个点把比它小的全放左边比它大的全放右边”。我们大概可以这样做：一个flag从最左端开始移动，一个flag从最右端开始移动，当碰到一个左侧的点大于被选择点，并且一个右侧的点小于被选择的点时，交换它们。
当然，在执行的时候我们可以把选中的那个点放在数组的最右边，当然也可以不动，比如我们直接选择最左端和最右端的点当作我们的判断点。
那么我们来实现一哈：

//先实现一下主函数
template <typename T>
void QuickSort( T a[ ], int n )
{
    if (n <= 1)
        return;
    Qsort( a, 0, n-1 );
}  //是的，这就完了

哈哈，我们赶紧来实现一哈核心功能Qsort()：

template <typename T>
void Qsort( T a[ ], int Left, int Right )
{
    if ( Left >= Right)  //说明已经不能再divide了
        return;
    int i = Left, j = Right;
    T pivot = a[ Left ];  //选最左端点为pivot
    while ( i < j )
    {
        while ( i < j && a[ j ] >= pivot )  //这里需要 i < j 为了控制不过界
            --j;  //当a[ j ]比pivot大时，继续递减，直到减到不满足条件
        a[ i ] = a[ j ];  //把 j 位置上的值赋给 i ，而第一个i正是pivot
        while ( i < j && a[i] >= pivot )
            ++i;
        a[ j ] = a[ i ];  //继上，把这个i赋给j上一次的位置，很巧妙吧
    }
    a[ i ] = pivot;
    Qsort( a, Left, i - 1 );
    Qsort( a, i + 1, Right );  //分别去i-1和i+1，跳过i
}

简单分析一下，
1）为什么要从j开始计算呢？因为我们把pivot设在了最左端，这个位置一定要当作第一个被交换的位置，才能保证程序的顺利运行（所以如果pivot在最右端，你会了吗？）。
2）为什么最后是a[ i ] = pivot;结尾呢？很简单，回到程序，我们先从j计算，再计算i的移动，那么很显然是把i的位置和pivot交换啊~~

不过，正如很多书上所说（就当是吧），因为现实中很多序列并不是完全无序的，取第一个比较冒险，有可能出现最差解，所以有以下2种取法：
1.随机（我感觉挺好的，他们说计算量耗费大）。
2.3数取中值：就是第1，最后，中间3个元素取他们的中值作为pivot。实现方法很简单：

void mid3( T a[], int L, int R )
{
    int C = ( L + R ) / 2;
    if ( a[ L ] > a[ C ] )
        swap( a[ C ], a[ L ] );
    if ( a[ C ] > a[ R ] )
        swap( a[ C ], a[ R ] );
    if ( a[ R ] > a[ L ] )
        swap( a[ R ], a[ L ] );
    swap( a[ C ], a[ Left + 1 ] );
    return a[ Left + 1 ] ;
}

先讲结果：分别把左中右3个数排序，然后把中数放到第2个位置。当然调用的时候也需稍作调整，此处不再赘述。
一个不需要注意的地方是：这3个数比较并无特别的规则，只需要两两比较就好了（C₃²=3而已）。

时间复杂度我就不证了，最坏是O(n²)，当每次pivot都取第一个的时候。

堆排序我们先不讲了，等到聊到优先队列的时候再说吧。那么，我们第一个话题似乎就结束了~~

BTW，你有没有觉得用c++写这段代码好多啊，要不然，我们用python大概写一下？

def qsort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a)//2]  # 使用py3.x，2.x的话不需要//
    left = [x for x in a if x < pivot]
    mid = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return qsort(left) + mid + qsort(right)  # 已经实现一次划分了

是不是有点恐怖，这么复杂的算法，仅仅不到10行······