剑指Offer - 九度1516 - 调整数组顺序使奇数位于偶数前面

http://www.cnblogs.com/zhuli19901106/p/3450578.html
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

既然要求顺序不能变，那就得保证从前往后扫描。可以用一个数组扫描两次，先后记录奇数和偶数；或者用两个数组扫描一次，记录奇数和偶数。之后再将数组写回原数组，释放额外空间即可。这种方法时间和空间复杂度均为O(n)，虽然很土，但简单易懂。

我们可以维护两个指针，第一个指针初始化为数组的第一个数字，它只向后移动；第二个指针初始化为数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。

http://blog.csdn.net/sunnyyoona/article/details/16360149

void SortOddBeforeEven(int *number,int n){
    int left = 0,right = n-1;
    //下标
    int oIndex = 0,eIndex = 0;
    //二分遍历
    while(left < right){
        //从左边直到第一个偶数
        while(left < right && (number[left] % 2 != 0)){
            left++;
        }
        //从右边直到第一个奇数
        while(left < right && (number[right] % 2 == 0)){
            right--;
        }
        //奇偶数交换
        if(left < right){
            int temp;
            temp = number[left];
            number[left] = number[right];
            number[right] = temp;
        }
    }

http://bylijinnan.iteye.com/blog/1441092

// Use O(n) space, not good.

    //O(n)--Odd number is inserted from front,Even number from tail.  
    public static void sort(int[] x){  
        if(x==null||x.length==0){  
            return;  
        }  
        int len=x.length;  
        int[] tmp=new int[len];  
        int oddPos=0;  
        int evenPos=len-1;  
        for(int i=0;i<len;i++){  
            if(!isEven(x[i])){  
                tmp[oddPos++]=x[i];  
            }else{  
                tmp[evenPos--]=x[i];  
            }  
        }  
        System.arraycopy(tmp, 0, x, 0, len);  
    }  

 7 int main()
 8 {
 9     vector<int> b, c;
10     int n, i, tmp;
11     
12     // this solution is O(n) both in time and space.
13     while(scanf("%d", &n) == 1){
14         b.clear();
15         c.clear();
16         for(i = 0; i < n; ++i){
17             scanf("%d", &tmp);
18             tmp % 2 ? b.push_back(tmp) : c.push_back(tmp);
19         }
20         for(i = 0; i < c.size(); ++i){
21             b.push_back(c[i]);
22         }
23         c.clear();
24         printf("%d", b[0]);
25         for(i = 1; i < b.size(); ++i){
26             printf(" %d", b[i]);
27         }
28         b.clear();
29         printf("\n");
30     }
31     
32     return 0;
33 }

http://www.acmerblog.com/offer-6-2429.html
http://zhedahht.blog.163.com/blog/static/25411174200741295930898/

题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

因此我们可以维护两个指针，第一个指针初始化为数组的第一个数字，它只向后移动；第二个指针初始化为数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。

３．在函数Reorder中，用函数指针func指向的函数来判断一个数字是不是符合给定的条件，而不是用在代码直接判断（hard code）。这样的好处是把调整顺序的算法和调整的标准分开了（即解耦，decouple）。当调整的标准改变时，Reorder的代码不需要修改，只需要提供一个新的确定调整标准的函数即可，提高了代码的可维护性。例如要求把负数放在非负数的前面，我们不需要修改Reorder的代码，只需添加一个函数来判断整数是不是非负数。这样的思路在很多库中都有广泛的应用，比如在ＳＴＬ的很多算法函数中都有一个仿函数（functor）的参数（当然仿函数不是函数指针，但其思想是一样的）。如果在面试中能够想到这一层，无疑能给面试官留下很好的印象。