终于有时间坐下来写一写这半年学习的算法，否则又要白学了。
1.Partition函数：
快排中最重要的是划分算法Partition(A,l,r)：该算法输入是数组A，以及我们在这次划分中考虑的元素的范围——从下标为l的元素考虑到下标为r的元素。假设总是选取下标为r的元素作为轴p，那么一次划分结束后，p元素左边的元素都比它小，右边的元素都比它大。例如：有数组2 3 1 3 4 2 ，选取末尾红色的2为轴，经过一次划分后数组变为2 1 2 3 4 3，可以看到划分后轴元素2的左边都是小于等于2的元素，右边都是大于2的元素。
记住算法中重要的变量就可以快速的写出算法，划分函数中主要有三个：i,j,p；p就是上述说的轴元素，假设每次都选取数组最后一个元素作为轴。在划分过程中j是游标，从l遍历到r；i指向比轴p大的元素中最左边的那个，如果发现j指向的元素比轴p小了，就和i指向的元素互换，i向后移动。见下图，红色的2是选中的轴元素，i指向的3是比2大的第一个元素，当前j遍历的元素是1，比轴元素2小，所以将这个1与i指向的元素3交换，得到右边交换后的图。所以这里，我们可以这样理解i，它维护了一个大于p和小于等于p的元素的分界线，并且它指向的元素总是大于p并且“准备”与比p小（或者等于p）的元素交换的。
2.quick_sort函数
有了partition函数，快排就很容易写出来了，就是三个步骤：调用partition，递归快排轴左边的元素序列，递归调用轴右边的元素序列。代码如下：
1 #include <iostream> 2 using namespace std; 3 int A[10] = {2,5,4,2,1,4,7,8,4,3}; 4 5 void Swap(int A[10],int i,int j) 6 { 7 int temp = A[i]; 8 A[i] = A[j]; 9 A[j] = temp; 10 } 11 int Partition(int A[10],int l,int r) 12 { 13 int p = A[r]; //选取最后一个元素最为轴元素 14 int i = l; 15 for(int j = l;j <= r-1;j++) 16 { 17 if(A[j] <= p) 18 { 19 Swap(A,i,j); //如果j指向的元素比轴p小，就和i指向的元素互换位置 20 i++; 21 } 22 } 23 Swap(A,i,r); //每一次partition的过程中，轴元素p都被放到最终的位置上 24 return i; 25 } 26 27 void quick_sort(int A[10],int l,int r) 28 { 29 if(l < r){ 30 int pivot = Partition(A,l,r); 31 quick_sort(A,l,pivot-1); 32 quick_sort(A,pivot+1,r); 33 } 34 return; 35 } 36 int main() 37 { 38 quick_sort(A,0,9); 39 for(int i = 0;i <= 9;i++) 40 cout << A[i]<<" "; 41 cout <<endl; 42 }
说一下partition这个函数，除了在快排中，还有很多其他情况都可以应用。比如《算法导论》Problems8-4的“水壶问题”：有一堆红色水壶和蓝色水壶，所有的红色水壶中水量不等，所有的蓝色水壶中水量不等。对于任意一个红色水壶，对应一个蓝色水壶水量和它相等，比较一个蓝色水壶和红色水壶中水量多少记为一次操作，同色水壶间不能进行水量比较。问多少进行多少次操作，能够把所有红色水壶和蓝色水壶配对。
这个问题就可以用partition的思想：任意选取一个红色水壶，把它和所有的蓝色水壶比较一遍水量，比它少的放一堆，多的放一堆，相等的单独拿出来，再用这个和它水量相等的蓝色水壶和所有的红色水壶比较一遍，同样分成比它小的和比它大的，这样所有的水壶就被分成三堆，其中一堆为一对已经配对的水壶，对剩下两堆水壶进行递归操作，直到所有水壶都配对。
最后记一下快排的性质：最优时间复杂度O(nlogn),最坏时间复杂度O(n^2)，不稳定排序。之所以速度快是因为它的过程符合现代计算机的cache机制，即每次需要操作的元素在计算机中物理位置很近，通常可以一次性取进cache。