题目
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
分析
暴力法
最简单能想到的就是从前到后依次遍历若发现是偶数，先保存当前元素，将后面全部往前移动，然后把保存的元素给到最后那个位置。时间复杂度为O(n2)，空间复杂度为O(1);
C
#include<stdio.h> #include<assert.h> //暴力法 void ReordeOddEven(int* pData, unsigned int length) { assert(NULL != pData); assert(length > 0); int i = 0; int j = 0; for(i = 0; i < length; i++) { if((pData[i] & 1) == 0)//&优先级低于==所以务必加括号，否则永远不成立 { int tmp = pData[i]; for(j = i; j < length - 1; j++) { pData[j] = pData[j + 1]; } pData[j] = tmp; } } } void Print(int* n, int length) { int i = 0; for(i = 0; i < length; i++) { printf("%d ", n[i]); } printf("\n"); } int main() { int n[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int length = sizeof(n) / sizeof(n[0]); ReordeOddEven(n, length); Print(n, length); return 0; }
双指针
我们还可以用俩个指针。分别指向头和尾巴。
让start指针向后走找偶数，让end指针向前走找奇数。循环条件：start<end
C
#include<stdio.h> #include<assert.h> void swap(int* n , int i, int j) { int tmp = n[i]; n[i] = n[j]; n[j] = tmp; } void ReordeOddEven(int* pData, unsigned int length) { assert(NULL != pData); assert(length > 0); int start = 0; int end = length - 1; while(start < end) { while(start < end && (pData[start] & 1) == 1)//如果是奇数就一直找 { start++; } while(start < end && (pData[end] & 1) == 0)//如果是偶数就一直找 { end--; } if(start < end) { swap(pData, start, end); } } } void Print(int* n, int length) { int i = 0; for(i = 0; i < length; i++) { printf("%d ", n[i]); } printf("\n"); } int main() { int n[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int length = sizeof(n) / sizeof(n[0]); ReordeOddEven(n, length); Print(n, length); return 0; }
具有扩展性的双指针
分析上面代码我们发现核心就只有俩段代码(pData[start] & 1)和(pData[end] & 1)，我们把这个代码封装成一个函数，这个地方直接调用封装好的函数就ok了。
C
#include<stdio.h> #include<assert.h> #include<stdbool.h> bool func(int n) { return (n & 1) == 0; } void swap(int* n, int i, int j) { int tmp = n[i]; n[i] = n[j]; n[j] = tmp; } void ReordeOddEven(int* pData, unsigned int length) { assert(NULL != pData); assert(length > 0); int start = 0; int end = length -1; while(start < end) { while(start < end && func(pData[start]) == false) { start++; } while(start < end && func(pData[end]) == true) { end--; } if(start < end) { swap(pData, start, end); } } } void Print(int* n, int length) { int i = 0; for(i = 0; i < length; i++) { printf("%d ", n[i]); } printf("\n"); } int main() { int n[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int length = sizeof(n) / sizeof(n[0]); ReordeOddEven(n, length); Print(n, length); return 0; }
本章完！
