首页 > 代码库 > 调整数组奇偶顺序

调整数组奇偶顺序

 

  • 题目描述:

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,是所有的奇数位于数组的前半部分,所有偶数位于数组的后半部分。

  • 分析:

    我们要做的是调整数组中元素的顺序,所以显然函数中主要的操作是交换元素,也就是交换奇数和偶数,使奇数位于偶数前边。在前边各种数组的题目中,我们常用到使用两个指针的方法,一个从前向后移动,一个从后向前移动。当前边的指针指向一个偶数,而后边的指针指向一个奇数时,交换两个元素,直到两个指针相遇为止。

    void ReorderArray(int* pData, unsigned int length)
    {
    	if (pData =http://www.mamicode.com/= NULL || length <= 0)
    		return;
    
    	unsigned int Begin = 0;
    	unsigned int End = length - 1;
    	while (Begin < End)
    	{
    		while (Begin < End && (pData[Begin] & 1) != 0)
    			++Begin;
    
    		while (Begin < End && (pData[End] & 1) == 0)
    			--End;
    
    		if (Begin < End)
    		{
    			int temp = pData[Begin];
    			pData[Begin] = pData[End];
    			pData[End] = temp;
    		}
    	}
    }
    

    值得注意的是: 在判断数字的奇偶时,往往使用位运算“&1”,得1说明是奇数,反之为偶数;原因在于,只有当一个数的二进制表示中的最低位为1时这个数才是奇数。而使用取余%计算远远不如位运算效率高。
    另附一个小技巧:在求余运算中,如果被求余数是2的整数次幂,可以用位运算来进行转换,从而得到比较高的效率。
    n % m => n & (m - 1)
    例如:求 n % 32 ,可以将其转换为 n & (32-1)

调整数组奇偶顺序