大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
一 题目：调整数组顺序使奇数位于偶数前面
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
二 解题思路
如果不考虑时间复杂度，最简单的思路应该是从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于每碰到一个偶数就需要移动O(n)个数字，因此总的时间复杂度是O(n2)。
这里可以参考快速排序的思想，快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
三 代码实现
void Swap(int *p, int *q) { int temp = *p; *p = *q; *q = temp; } void ResetArray(int a[], int nLen) {
if (NULL == a || nLen <= 0)
{
return;
} int *left = a; int *right = &a[nLen -1]; while (left < right) { while(*left % 2 && (left < right)) { left ++; } while ((*right % 2) == 0 && (left < right)) { right --; } Swap(left++, right--); } } void main() { int a[] = {1,2,3,4,5,6,7,8,9}; ResetArray(a, 9); return; }
四 可扩展实现
如果把题目改成把数组中的数分为两部分，能被3整除的数都在不能被3整除的数的前面。面对需求的变化，我们发现代码变化的部分很小，因此从可扩展性的角度考虑，我们可以改写上面的代码如下，这里利用回调函数来实现。
typedef bool (*Proc)(int *); bool CmpCondition_1(int *p) { if (*p % 2) { return true; } return false; } bool CmpCondition_2(int *p) { if (*p % 3) { return false; } return true; } void ResetArray(int a[], int nLen, Proc fun) { if (NULL == a || nLen <= 0 || NULL == fun) { return; } int *left = a; int *right = &a[nLen -1]; while (left < right) { while(fun(left) && (left < right)) { left ++; } while (!fun(right)&& (left < right)) { right --; } Swap(left++, right--); } } void PrintArry(int *a, int nLen) { for (int i = 0;i < nLen; i ++) { cout << a[i] << " "; } cout << endl; } void main() { int a[] = {1,2,3,4,5,6,7,8,9}; cout <<"原始数组："; PrintArry(a, 9); ResetArray(a, 9,CmpCondition_1); cout <<"奇数放前面，偶数方面："; PrintArry(a, 9); ResetArray(a, 9,CmpCondition_2); cout <<"被3整除的放前面："; PrintArry(a, 9); return; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120163.html原文链接：https://javaforall.net
