题目： 2n个数，一半奇数，一半偶数，设计一个程序让奇数位上的数是奇数，偶数位上的是偶数

要求：时空复杂度尽量低

看到群里发的这个题目，随手写了个一个答案：

def swap(a, i, j): 
    a[i] = a[i] + a[j]
    a[j] = a[i] - a[j]
    a[i] = a[i] - a[j]
        
def Fun():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list
    i,j = 0,1
    nSwap = 0
    while nSwap < 50 and max(i,j) < 100:
        if the_list[i] % 2 != 0 and the_list[j] % 2 == 0 :
            swap(the_list,i,j)
            i += 2
            j += 2
            nSwap += 1
        elif the_list[i] % 2 == 0 :
            i += 2
        elif the_list[j] % 2 != 0 :
            j += 2
    print "sorted:", the_list

经penny等群友的提醒，优化一下，第二版：

def Fun2():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list 
    for i,j in zip([pos for pos in range(0,100,2) if (the_list[pos] + pos) % 2 != 0],
                              [pos for pos in range(1,100,2) if (the_list[pos] + pos) % 2 != 0]):
        the_list[i], the_list[j] = the_list[j], the_list[i]
    print "sorted:", the_list

附：penny发了一个点积的优化

A[]={<0,4>,<3,5>,<8,3>}
B[]={<3,5>,<9,3>}

C=A*B = {<3,25>}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;	
	if(A[i].index == B[j].index)
	{
		C[k].index = A[i].index;
		C[k].value = A[i].value * B[j].value
		k++
	}
	else if(A[i].index < B[j].index)
	{
		i++;
	}
	else if(A[i].index > B[j].index )
	{
		j++;
	}
}

A_I[]={0,3,8}
B_I[]={3,9}
A_V[]={4,5,9}
B_V[]={5,3}
for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	if(A_I[i] == B_I[j])
	{
		C[k].index = A_I[i];
		C[k].value = A_V[i]*B_V[j];
	}
	else if(A_I[i] < B_I[j])
	{
		i++;
	}
	else
	{
		j++;
	}
}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	i=0;
	j=0;
	bool equal  =  A_I[i] == B_I[j];
	bool smaller=  A_I[i] < B_I[j]; 
	bool bigger =  A_I[i] > B_I[j];
	C[k].index  =  equal*A_I[i];
	C[k].value  =  equal*A_V[i]*B_V[j];
	k+=equal;
	i+=equal;
	j+=equal;
        i+=smaller;
	j+=biger;	
}