1 /************************************************************************* 2     > File Name: RearrangeArray.cpp 3     > Author: zhoukang1991 4     > Mail: zhoukang199191@126.com  5     > Created Time: 2014年08月28日 星期四 21时50分54秒 6  ************************************************************************/ 7  8 #include <iostream> 9 #include <vector>10 #include <algorithm>11 using namespace std;12 13 //keep the original sequence14 //类似于插入排序，不过是从左到右处理每次找到不满组15 //条件的就往后寻找满足的，并且数组右移16 void rightrotate(vector<int> &arr,int outofplace,int cur){17     int tmp = arr[cur];18     for(int i = cur ; i > outofplace ; --i){19         arr[i] = arr[i-1];20     }21     arr[outofplace] = tmp;22 }23 24 void rearrangeArray_1(vector<int> &arr){25     int n = arr.size();26     int outofplace = -1;27     for(int i = 0 ; i < n ; ++i){28         if(outofplace >= 0){29             if(((arr[i] >= 0) && (arr[outofplace] < 0)) || ((arr[i]<0)&&(arr[outofplace]>=0))){30                 rightrotate(arr,outofplace,i);31                 if(i-outofplace > 2){32                     outofplace = outofplace+2;33                 }34                 else{35                     outofplace = -1;36                 }37             }38         }39         if(outofplace == -1){40             if(((arr[i] >= 0)&&(!(i&0x01)))||((arr[i] < 0)&&(i & 0x01))){41                 outofplace = i;42             }43         }44     }45 }46 47 //不需要保持原来顺序48 //类似于快速排序：两个指针从前往后开始遍历，不满足条件的就交换49 int check(int v,int id){50     if((v >= 0)&&(!(id & 0x01))){51         return 1;52     }53     else if((v < 0) && (!(id & 0x01))){54         return -1;55     }56     return 0;57 }58 void rearrange_2(vector<int> &arr){59     int n = arr.size();60     int left,right;61     while(left < n && right < n){62         for(;left < n ; ++left){63             if(check(arr[left],left) == 1){64                 break;65             }66         }67         for(;right < n ; ++right){68             if(check(arr[right],right) == -1){69                 break;70             }71         }72         swap(arr[left],arr[right]);73         left++;74         right++;75     }76 }77 78 int main(){79     return 0;80 }