学步园

void swap(int* a,int* b)
{
    *a = *a ^ *b;    //a、b中不同位
    *b = *a ^ *b;    //b = a
    *a = *a ^ *b;    //a = b
}
void ArrangArray(int* StartPos,int* EndPos)
{
    //Step1先将小于零的放在最左边，大于等于0的数不区分，都放在右边
    int* low = StartPos;
    int* high = EndPos;
    while(low < high)
    {
        while( *low < 0 && low < high ) low++;
        while( *high >= 0 && low < high ) high--;
        if(low < high)
            swap(low,high);
    }//由于里面循环和外面都是对low和high的判断，我个人认为是    n
    //循环结束时，low一定等于high，且指向大于等于0的数   
    //
    high = EndPos;
    while(low < high)
    {
        while( *low == 0 && low < high ) low++;
        while( *high > 0 && low < high ) high--;
        if(low < high)
            swap(low,high);
    }//同理这里也是n
}
int main()
{
    int array[10] = {-1,3,0,2,-5,0,-3,4,0,-8};
    ArrangArray(array,array + 9);
}

先看这个的复杂度 。
个人认为是O（n），如果不是，请指教。
快排的三个步骤
1 找到序列中用于划分序列的元素
2. 用元素划分序列
3. 对划分后的两个序列重复1,2两个步骤指导序列无法再划分
T(n) = 2*T(n/2) + n （表示将长度为n的序列划分为两个子序列，每个子序列需要T(n/2)
                         的时间，而划分序列需要n的时间）
而 T(1) = 1            （表示长度为1的序列无法划分子序列，只需要1的时间即可） 
   T(n) = 2^logn + logn * n   （n被不断二分最终只能二分logn次（最优的情况,每次选取
                                的元素都均分序列））
        = n + nlogn
因此T(n) = O(nlogn)。
我的理解是
T(n) = 2*T(n/2) + n
那么 O（n）= 2^logn + nlogn = n + nlogn.
把一个序列分成两个序列的过程是O（n）  而需要logn次。所以  本题复杂度为O（n）。
T（n）= T（n/2） + O（1） 这样的次数为logn 则为O（logn），参考二分查找。
还有logn级别的算法有如下特点
while(count < n)
{
         count /=2;
}