快排是一种使用广泛的排序，它比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个数比较并无特别的规则，只需要两两比较就好了（C32=3而已）。
时间复杂度我就不证了，最坏是O(n2)，当每次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行······
网友评论