快速排序

终于有时间坐下来写一写这半年学习的算法，否则又要白学了。

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，递归快排轴左边的元素序列，递归调用轴右边的元素序列。代码如下：

   

#include <iostream>
using namespace std;
int A[10] = {2,5,4,2,1,4,7,8,4,3};

void Swap(int A[10],int i,int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
int Partition(int A[10],int l,int r)
{
    int p = A[r]; //选取最后一个元素最为轴元素
    int i = l;
    for(int j = l;j <= r-1;j++)
    {
        if(A[j] <= p)    
        {
            Swap(A,i,j);   //如果j指向的元素比轴p小，就和i指向的元素互换位置
            i++;
        }
    }
    Swap(A,i,r);    //每一次partition的过程中，轴元素p都被放到最终的位置上
    return i;
}

void quick_sort(int A[10],int l,int r)
{
    if(l < r){
        int pivot = Partition(A,l,r);
        quick_sort(A,l,pivot-1);
        quick_sort(A,pivot+1,r);
    }
    return;
}
int main()
{
    quick_sort(A,0,9);
    for(int i = 0;i <= 9;i++)
        cout << A[i]<<" ";
    cout <<endl;
}

    说一下partition这个函数，除了在快排中，还有很多其他情况都可以应用。比如《算法导论》Problems8-4的“水壶问题”：有一堆红色水壶和蓝色水壶，所有的红色水壶中水量不等，所有的蓝色水壶中水量不等。对于任意一个红色水壶，对应一个蓝色水壶水量和它相等，比较一个蓝色水壶和红色水壶中水量多少记为一次操作，同色水壶间不能进行水量比较。问多少进行多少次操作，能够把所有红色水壶和蓝色水壶配对。

    这个问题就可以用partition的思想：任意选取一个红色水壶，把它和所有的蓝色水壶比较一遍水量，比它少的放一堆，多的放一堆，相等的单独拿出来，再用这个和它水量相等的蓝色水壶和所有的红色水壶比较一遍，同样分成比它小的和比它大的，这样所有的水壶就被分成三堆，其中一堆为一对已经配对的水壶，对剩下两堆水壶进行递归操作，直到所有水壶都配对。

    最后记一下快排的性质：最优时间复杂度O(nlogn),最坏时间复杂度O(n^2)，不稳定排序。之所以速度快是因为它的过程符合现代计算机的cache机制，即每次需要操作的元素在计算机中物理位置很近，通常可以一次性取进cache。