void rev(vector &arr, int i, int j){
while(i < j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++;
j--;
}
return;
}
void Helper(vector &arr, int left, int right){
if(left == right) return;
int mid = left + (right-left)/2;
Helper(arr, left, mid);
Helper(arr, mid+1, right);
int i = mid, j = mid+1;
if(arr[i] < 0 || arr[j] > 0) return;
if(arr[i] <= 0 && arr[j] >= 0) return;
for(; i >= left && arr[i] >= 0; i--){}
for(; j <= right && arr[j] <= 0; j++){}
i++;
j--;
rev(arr, i, j);
rev(arr, i, i+j-mid-1);
rev(arr, i+j-mid, j);
return;
}
这个应该是 nlogn 的.