#coding=gbk
# 题目：输入一个整数数组，调整数组中数字的顺序，
# 使得所有奇数位于数组的前半部分， 所有偶数位于数组的后半部分。
# 要求时间复杂度为O(n)
# 分析:
# 时间复杂度为O(n),意味着,只能对数组进行一次扫描.
# 对数组进行一次扫描,至少有四种方式:
# (1) 从左向右
# (2) 从右向左
# (3) 从左右两个方向同时向当中扫描,在中间相遇
# (4) 从中间向两边扫描.
# 这个概念有可以做出很多花样的题目.
# 本题实质:
# 把偶数"看成"大于奇数,用quick sort 的一遍扫描就搞定了.
#-------------------------------------------------------
def partition( A ):
N = len( A )
L = 0
R = N-1
while L<R:
I = L ; J = R
#从左向右找到一个偶数停下来
while A[I] % 2 == 1 and I<R:
I += 1
#从右向左找到一个奇数停下来
while A[J] % 2 == 0 and J>=I:
J -= 1
if I<=J:
A[I], A[J] = A[J],A[I]
I = I+1 ; J = J -1
L = I
R = J
from random import randint
N = 13 ;
# 产生 N 个随机整数
A =[ ]
for I in range(0,N):
x = randint(-N*5,N*5)
if not ( x in A ):
A.append( x )
print ("整理前 A=",A)
partition( A )
print ("整理后 A=",A)
-- 结果 --
整理前 A= [-3, -8, -28, -38, -24, 64, -20, -27, -39, -31, 28, 21, -26]
整理后 A= [-3, 21, -31, -39, -27, 64, -20, -24, -38, -28, 28, -8, -26]
public class OddEven {
public static void main(String [] args){
int [] a = {1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10};
int left = 0;
int right = a.length - 1;
int l = 0;
int r = a.length - 1;
while(l < r){
while(a[l] % 2 == 1 && l < right)
l++;
while(a[r] % 2 == 0 && r > left)
r--;
if(l < r){
int t = a[l];
a[l] = a[r];
a[r] = t;
l++;
r--;
}
}
for(int c: a){
System.out.println(c);
}
}
}
