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（2n），这样分析对不对？ |
楼主
标题置顶
标题高亮
