输入一个整数数组,实现一个函数来调整改数组中数字的顺序。使得所有奇数位于数组的前半部分。偶数位于数组的后半部分。
- 思路1: 遍历数组，如果当前数字为偶数，则把它之后的所有数字均向前移动一位，然后当前数字移动到末尾。这样的时间复杂度为O(n2)。
- 思路2: 分别使用2个指针，一个指针指向数组的头部，一个指向数组的尾部。比较头指针和尾指针指向的数值。如果头指针指向的是奇数则头指针向后移动，直到指向偶数。如果尾指针如果指向偶数，则一直向前移动，直到指向奇数。
void sorted(int*array,int length){
if (array == nullptr || length ==0) {
return;
}
int*pBegin = array;
int*pEnd = array+ length-1;
//1.只要尾指针大于头指针跳出 2.只要头指针指向奇数就向后移动，只要尾指针指向偶数就向前移动 3.只要头指针大于尾指针就交互两个指针指向的值
while (pBegin<pEnd) {
//如果是奇数则一直走。直到走
while (pBegin<pEnd&&(*pBegin&0x1)!=0) {
pBegin++;
}
//偶数则一直走，直到遇到奇数
while (pBegin<pEnd&&(*pEnd&0x1)==0) {
pEnd--;
}
if (pBegin<pEnd) {
int numbers = *pBegin;
*pBegin = *pEnd;
*pEnd = numbers;
}
}
}
现在我们要让排序规则改变。我们要把规则抽象出来。抽象成一个函数指针。
void sorted(int*array,int length,bool(*func)(int)){
if (array == nullptr || length ==0) {
return;
}
int*pBegin = array;
int*pEnd = array+ length-1;
//1.只要尾指针大于头指针跳出 2.只要头指针指向奇数就向后移动，只要尾指针指向偶数就向前移动 3.只要头指针大于尾指针就交互两个指针指向的值
while (pBegin<pEnd) {
//如果是奇数则一直走。直到走
while (pBegin<pEnd&& !func(*pBegin)) {
pBegin++;
}
//偶数则一直走，直到遇到奇数
while (pBegin<pEnd&&func(*pEnd)) {
pEnd--;
}
if (pBegin<pEnd) {
int numbers = *pBegin;
*pBegin = *pEnd;
*pEnd = numbers;
}
}
}
bool isEvent(int a){
return (a&0x1)==0;
}
