面试题精选100题(29)-调整数组顺序使奇数位于偶数前面[算法]

http://www.acmerblog.com/interview-9-2427.html
Also check http://zhedahht.blog.163.com/

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

要求的是把奇数放在数组的前半部分，偶数放在数组的后半部分，因此所有的奇数应该位于偶数的前面。也就是说我们在扫描这个数组的时候，如果发现有偶数出现在奇数的前面，我们可以交换他们的顺序，交换之后就符合要求了。

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

２．这道题有很多变种。这里要求是把奇数放在偶数的前面，如果把要求改成：把负数放在非负数的前面等，思路都是都一样的。

10	void ReorderOddEven(int *pData, unsigned int length)

11

{

12	if(pData == NULL || length == 0)

13

return;

14

15	Reorder(pData, length, isEven);

16

}

20	// satisfy func in the first part, otherwise in the second part

21	// Input: pData  - an array of integers

22	//        length - the length of array

23	//        func   - a function

24	25 void Reorder(int *pData, unsigned int length, bool (*func)(int))

26

{

27	if(pData == NULL || length == 0)

28

return;

29

30	int *pBegin = pData;

31	int *pEnd = pData + length - 1;

32

33	while(pBegin < pEnd)

34

{

35	// if *pBegin does not satisfy func, move forward

36	if(!func(*pBegin))

37

{

38	pBegin ++;

39

continue;

40

}

41

42	// if *pEnd does not satisfy func, move backward

43	if(func(*pEnd))

44

{

45

pEnd --;

46

continue;

47

}

48

49	// if *pBegin satisfy func while *pEnd does not,

50	// swap these integers

51	int temp = *pBegin;

52	*pBegin = *pEnd;

53	*pEnd = temp;

54

}

55

}

56

57	/////////////////////////////////////////////////////////////////////////

58	// Determine whether an integer is even or not

59	// Input: an integer

60	// otherwise return false

61	/////////////////////////////////////////////////////////////////////////

62	bool isEven(int n)

63

{

64	return (n & 1) == 0;

65

}