# Interview Questions 3: Sort negative and positive numbers

1,71,-5,9,-11,15

-5,-11,1,71,9,15

```void reorder(std::vector<int> &nums) {
int len = nums.size();
std::vector<int> nums_copy = nums;
int cnt = 0;
for(int i = 0; i < len; ++i) {
if(nums_copy[i] < 0) nums[cnt++] = nums_copy[i];
}
for(int i = 0; i < len; ++i) {
if(nums_copy[i] > 0) nums[cnt++] = nums_copy[i];
}
return ;
}
```

```int reorder3(std::vector<int> &nums, int p, int r) {
if(p > r) {
return -1;
}
if(p == r) {
if(nums[p] < 0)
return -1;
else
return p;
}
if(r - p == 1) {
if(nums[r] < 0 && nums[p] > 0) {
std::swap(nums[p], nums[r]);
return r;
}
if(nums[r] > 0 && nums[p] < 0) {
return r;
}
if(nums[r] < 0 && nums[p] < 0) {
return -1;
}
return p;
}
// at least there are three elements
int q = p + (r - p) / 2;
int left  = reorder3(nums, p, q - 1);
int right = reorder3(nums, q, r);

if(-1 == left) return right;
if(-1 == right) {
flip(nums, left, q, r); // flip reorders the cross parts in linear time
return r + 1 - (q - left);
}
flip(nums, left, q, right - 1);
return right - (q - left);
}
```

（全文完，转载时请注明作者和出处）

（转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com，请勿用于任何商业用途）

Written on September 11, 2013