快速排序里的学问：快速排序的过程

通过前面问题以及引入了“信息熵”的概念，我们可以重新来理解排序的本质：

一组未排序的N个数字，它们一共有N!种重排，其中只有一种排列是满足题意的（譬如从大到小排列）。

换句话说，排序问题的可能性一共有N!种。任何基于比较的排序的基本操作单元都是“比较a和b”，这就相当于猜数字游戏里面的一个问句，显然这个问句的答案只能是“是”或“否”，一个只有两种输出的问题最多只能将可能性空间切成两半，根据上面的思路，最佳切法就是切成1/2和1/2（将数组切成一半）。也就是说，我们希望在比较了a和b的大小关系之后，如果发现a b也是剩下N!/2种可能性。

由于假设每种排列的概率是均等的，所以这也就意味着支持a b的也是N!/2个，换言之，a b的概率。

我们希望每次在比较a和b的时候，a b的概率是均等的，这样我们就能保证无论如何都能将可能性缩小为原来的一半的最优下界。

一个直接的推论是，如果每次都像上面这样的完美比较，那么N个元素的N!种可能排列只需要log2N!就排查完了，而log2N!近似于NlogN。这正是快排的复杂度。

快速排序的实现

我们先理解一下快速排序的工作机制吧，下面是《算法导论》里的快排：

QUICKSORT(A, p, r)
 if p 

快速排序算法的关键是PARTITION过程，它对A[p..r]进行就地重排：

PARTITION(A, p, r)
  x ← A[r]
  i ← p - 1
  for j ← p to r - 1
       do if A[j] ≤ x
             then i ← i + 1
                  exchange A[i] <-> A[j]
  exchange A[i + 1] <-> A[r]
  return i + 1


我们将上面的过程用C语言描述一下：

#include "stdio.h"
#include "math.h"
#include "stdlib.h"

void PrintArray(int *arr);
void swap(int *a,int *b);

int num = 10;

void QuickSort(int *arr, int beg, int end)
{
	if(beg 

初始数组:59 40 55 92 73 69 27 79 3 30
    sentinel = arr[9] = 30
    arr[6](27) <= sentinel(30)
    arr[8](3) <= sentinel(30)
排序过程:27 3 30 92 73 69 59 79 40 55
    sentinel = arr[1] = 3
排序过程:3 27 30 92 73 69 59 79 40 55
    sentinel = arr[9] = 55
    arr[8](40) <= sentinel(55)
排序过程:3 27 30 40 55 69 59 79 92 73
    sentinel = arr[9] = 73
    arr[5](69) <= sentinel(73)
    arr[6](59) <= sentinel(73)
排序过程:3 27 30 40 55 69 59 73 92 79
    sentinel = arr[6] = 59
排序过程:3 27 30 40 55 59 69 73 92 79
    sentinel = arr[9] = 79
排序过程:3 27 30 40 55 59 69 73 79 92
最后结果:3 27 30 40 55 59 69 73 79 92
Process returned 0 (0x0)   execution time : 0.564 s
Press any key to continue.


从程序的运行结果我们就可以很清晰地看出快速排序的工作工程：


定点sentinel设为数组最后一个元素30
把比30小的划成一个小组（27，3，30），并把它们放在数组的前面。
定点sentinel设为小组的最后一个，不包含30，即（27，3）中的3。
对小组原地排序，即（3，27）。这样就完成这个小组的排序了（3，27，30）。
定点sentinel再次设为数组最后一个元素55。
把小于55的元素找出来划分为另外的小组（40）。
那个小组的排序也已经完成（40，55）。
定点再设为73，同样分组（69，59，73），排序为（59，69，73）。
定点再设为79，分组（79）
完成排序：3 27 30 40 55 59 69 73 79 92


总结下快排的过程：随机选择一个元素做“轴元素”（上面的定点sentinel），将所有小于轴元素的移到左边，其余移到右边。根据这个过程，快排的第一次比较就是将一个元素和轴元素比较，这个时候显而易见的是，“大于”和“小于”的可能性各占一半。这是一次漂亮的比较。
						
延伸阅读
此文章所在专题列表如下：
快速排序里的学问：从猜数字开始
快速排序里的学问：再看看称球问题
快速排序里的学问：信息熵
快速排序里的学问：快速排序的过程
快速排序里的学问：霍尔与快速排序
快速排序里的学问：霍尔快排的实现
快速排序里的学问：枢纽元选择与算法效率
快速排序里的学问：随机化快排
						
本文地址：http://www.nowamagic.net/librarys/veda/detail/2390，欢迎访问原出处。