精选算法题(3)——奇偶数据分离

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

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

本题题目简单，但可以拓展一下思路。我用了三种方法，分别是vector存储、list存储、自定义链表存储，以验证计算效率。三种方法均采用遍历思路，遍历过程中将奇数存储在一个容器中，将偶数存储在另一个容器中，然后两容器合并即可。其中，我自定义了一个链表，将奇数链表的尾巴和偶数链表的头进行连接，节省了合并容器的过程，且具备较高的插入效率。文章后续有完整的速度对比方案。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
		val(x), next(NULL) {
	}
};

// 判断是否为奇数
bool isOdd(int number)
{
	return (bool)(number % 2);
}

// 奇数偶数分离
vector OddEvenSeparate1(vector input)
{
	vector output;
	vector evens;
	for (int i = 0; i < input.size(); ++i)
	{
		if (isOdd(input[i]))
		{
			output.emplace_back(input[i]);
		}
		else
		{
			evens.emplace_back(input[i]);
		}
	}
	output.insert(output.end(), evens.begin(), evens.end());
	return output;
}

// 奇数偶数分离
list OddEvenSeparate2(vector input)
{
	list output;
	list evens;
	for (int i = 0; i < input.size(); ++i)
	{
		if (isOdd(input[i]))
		{
			output.emplace_back(input[i]);
		}
		else
		{
			evens.emplace_back(input[i]);
		}
	}
	output.splice(output.end(), evens);
	return output;
}

// 奇数偶数分离
ListNode* OddEvenSeparate3(vector input)
{
	ListNode* output = new ListNode(-1);
	ListNode* evens = new ListNode(-1);
	ListNode* ohead = output;
	ListNode* ehead = evens;
	for (int i = 0; i < input.size(); ++i)
	{
		if (isOdd(input[i]))
		{
			ListNode* temp = new ListNode(input[i]);
			output->next = temp;
			output = output->next;
		}
		else
		{
			ListNode* temp = new ListNode(input[i]);
			evens->next = temp;
			evens = evens->next;
		}
	}
	ohead = ohead->next;
	ehead = ehead->next;
	output->next = ehead;
	return ohead;
}

int main()
{
	// 给定数组
	vector a(10000);
	for (int i = 0; i < a.size(); ++i)
	{
		a[i] = rand();
	}
	clock_t s, e;
	// 奇数偶数分离
	// 第一种方法
	s = clock();
	vector b1 = OddEvenSeparate1(a);
	e = clock();
	cout << "time1:" << e - s << endl;
	cout << "first:" << endl;
	for (auto i : b1)
	{
		cout << i << " ";
	}
	cout << endl;
	// 第二种方法
	s = clock();
	list b2 = OddEvenSeparate2(a);
	e = clock();
	cout << "time2:" << e - s << endl;
	cout << "second:" << endl;
	for (auto i : b2)
	{
		cout << i << " ";
	}
	cout << endl;
	// 第三种方法
	s = clock();
	ListNode* b3 = OddEvenSeparate3(a);
	e = clock();
	cout << "time3:" << e - s << endl;
	cout << "third:" << endl;
	while (b3 != nullptr)
	{
		cout << b3->val << " ";
		b3 = b3->next;
	}
	cout << endl;

	system("pause");
	return 0;
}

       当输入数组为10个数字时，验证下三种方法的准确性，如图1所示。

       当输入数组为1000万时，debug下的速度如图2所示。

       当输入数组为1000万时，release下的速度如图3所示。

       从上图可以看出，debug模式下自定义链表速度最快，但是release模式下vector速度最快，且自定义链表相对于STL中的list略快。

       如果代码有什么需要改进的或者有什么bug，欢迎评论留言，我会及时更正以免误导他人~

       如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！