博客

快速排序的关键在于区间划分，是指将待排序的数组原地进行区间划分，原理是：将待排序的数组的最后一个元素作为主元，将小于主元的数组元素放在数组较小的下标，将大于主元的数组元素放在较大的下标。主元放在两者之间。(

注意：是原地分区，所以分区后还是在待排序的数组里

)

在初始化时，默认分区的两个子数组元素个数均为0.对待排序的数组进行遍历，将每个元素从下标0开始与主元比较，大于主元的，就放在右边，小于主元的，放在左边。对于遍历到某一下标j，如果A[j]**小于**A[n]，此时已经有j-1元素按序放在A[0…j-1]中了，一些为小于主元的，一些大于主元的，但此时A[0…j-1]中没有主元，他们紧挨放的。当为A[j]时，此时就增加了一个元素，就把A[0…j]中第一个大于主元的值换到A[j]处，那么A[j]就被换到小于主元的那里，是此时最后一个小于主元的。直到遍历到倒数第二个元素。最后一个元素是主元，不不能遍历。循环结束。结束后，要把主元放到两者这件，此时就把第一个大于主元的值和主元位置对换，这样就达到把主元放到两者之间的目的了。

代码如下：

int Insert::Partition(vector<int> &coll,int p,int total)
{
    int left=p-1,right=0,temp=0;
    int pivot=coll[total];//主元，主元只用于比较，不用于迭代
    for(right=p;right<total;++right)
    {
        if(coll[right]<pivot)
        {
            ++left;
            temp=coll[left];
            coll[left]=coll[right];
            coll[right]=temp;
        }
    }
    coll[total]=coll[++left];
    coll[left]=pivot;
    return left;
}

注意：遍历时使用的是right,不能使用left,因为有时候right不一定为0，只能说是刚开始遍历时，left+1=right;若使用left会出错。此处P代表要遍历的起始下标（不一定是下标0），total是数组的最后一个下标。