Odd Event Sort 奇偶调序

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

事实上，若把奇数看做是小的数，偶数看做是大的数，那么按照题目所要求的奇数放在前面偶数放在后面，就相当于小数放在前面大数放在后面，联想到快速排序中的partition过程，不就是通过一个主元把整个数组分成大小两个部分么，小于主元的小数放在前面，大于主元的大数放在后面。

为何？比如partition的实现一中，如果最终是为了让整个序列元素从小到大排序，那么头指针理应指向的就是小数，而尾指针理应指向的就是大数，故当头指针指的是大数且尾指针指的是小数的时候就不正常，此时就当交换。

void OddEvenSort(int *pData, unsigned int length)
{
    if (pData == NULL || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while (pBegin < pEnd)
    {
        //如果pBegin指针指向的是奇数，正常，向右移
        if (IsOddNumber(*pBegin))  
        {
            pBegin++;
        }
        //如果pEnd指针指向的是偶数，正常，向左移
        else if (!IsOddNumber(*pEnd))
        {
            pEnd--;
        }
        else
        {
            //否则都不正常，交换
            swap(*pBegin, *pEnd);
        }
    }
}

http://836811384.iteye.com/blog/1978858

1. void SortOddBeforeEven(int *number,int n){  
2.     int left = 0,right = n-1;  
3.     //下标  
4.     int oIndex = 0,eIndex = 0;  
5.     //二分遍历  
6.     while(left < right){  
7.         //从左边直到第一个偶数  
8.         while(left < right && (number[left] % 2 != 0)){  
9.             left++;  
10.         }  
11.         //从右边直到第一个奇数  
12.         while(left < right && (number[right] % 2 == 0)){  
13.             right--;  
14.         }  
15.         //奇偶数交换  
16.         if(left < right){  
17.             int temp;  
18.             temp = number[left];  
19.             number[left] = number[right];  
20.             number[right] = temp;  
21.         }  
22.     }  
23. }  

一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来的正负数之间相对顺序，比如： input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求时间复杂度O(n),空间O(1)。

分析：如果本题没有这个要求“并且要求不改变原来的正负数之间相对顺序”，那么同奇偶数排序是一道题，但加上这个不能改变正负数之间的相对顺序后，便使得问题变得比较艰难了，若有兴趣，读者可以参考这篇论文《STABLE MINIMUM SPACE PARTITIONING IN LINEAR TIME》。

http://www.acmerblog.com/offer-6-2429.html

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

http://blog.csdn.net/fightforyourdream/article/details/17367821

1.     public static void process(int[] buf){  
2.         int buflen = buf.length;  
3.         int[] odd = new int[buflen];  
4.         int[] even = new int[buflen];  
5.         int j=0, k=0;  
6.         for(int i=0; i<buflen; i++){  
7.             if((buf[i]&1) == 1){  
8.                 odd[j++] = buf[i];  
9.             }else{  
10.                 even[k++] = buf[i];  
11.             }  
12.         }  
13.         for(int i=0; i<j; i++){  
14.             System.out.print(odd[i] + " ");  
15.         }  
16.         for(int i=0; i<k; i++){  
17.             if(i != k-1){  
18.                 System.out.print(even[i] + " ");  
19.             }else{  
20.                 System.out.print(even[i]);  
21.             }  
22.         }  
23.         System.out.println();  
24.     }  

http://www.cnblogs.com/easonliu/p/3645230.html 

7 int main() {
 9     vector<int> v;
10     queue<int> q;
11     int n;
12     while (scanf("%d", &n) != EOF) {
13         v.resize(n);
14         for (int i = 0; i < n; ++i) {
15             scanf("%d", &v[i]);
16         }
17         int count = 0;
18         for (int i = 0; i < n; ++i) {
19             if (v[i] % 2 == 1) {
20                 v[i - count] = v[i];
21             } else {
22                 ++count;
23                 q.push(v[i]);
24             }
25         }
26         for (int i = n - count; i < n; ++i) {
27             v[i] = q.front();
28             q.pop();
29         }
30         for (int i = 0; i < n; ++i) {
31             (i == n - 1) ? printf("%d\n", v[i]) : printf("%d ", v[i]);
32         }
33     }
34     return 0;
35 }

http://wdxtub.com/interview/14520595475403.html

//奇偶互换
void OddEvenSort2(int data[], int lo, int hi)
{
    int i = lo - 1;
    for (int j = lo; j < hi; j++)
    {
        //data[j]指向奇数，交换
        if ( IsOddNumber(data[j]) )
        {
            i = i + 1;
            swap(&data[i], &data[j]);
        }
    }
    swap(&data[i + 1], &data[hi]);
}

此解法一前一后两个指针同时向右扫描的过程中，也是一次遍历完成奇数偶数的重新排列，故时间复杂度也为O(n)。

02	int main()

03

{

04	int i, j, k, n, t ,arr[100000];

05	bool first;

06	while (scanf("%d", &n) != EOF)

07

{

08	first = true;

09

k = 0;

10	for (i = 0; i < n; i++)

11

{

12	scanf("%d", &t);

13	if (t & 1)

14

{

15	if (first)

16

{

17	printf("%d", t);

18	first = false;

19

}

20

else

21	printf(" %d", t);

22

}

23

else

24	arr[k++] = t;

25

}

26	for (int j = 0; j < k; j++)

27	printf(" %d", arr[j]);

28

}