题目描述：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路：
本题题目简单，但可以拓展一下思路。我用了三种方法，分别是vector存储、list存储、自定义链表存储，以验证计算效率。三种方法均采用遍历思路，遍历过程中将奇数存储在一个容器中，将偶数存储在另一个容器中，然后两容器合并即可。其中，我自定义了一个链表，将奇数链表的尾巴和偶数链表的头进行连接，节省了合并容器的过程，且具备较高的插入效率。文章后续有完整的速度对比方案。
测试代码：
#include <iostream> #include <string> #include <vector> #include <deque> #include <time.h> #include <list> 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<int> OddEvenSeparate1(vector<int> input) { vector<int> output; vector<int> 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<int> OddEvenSeparate2(vector<int> input) { list<int> output; list<int> 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<int> 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<int> a(10000); for (int i = 0; i < a.size(); ++i) { a[i] = rand(); } clock_t s, e; // 奇数偶数分离 // 第一种方法 s = clock(); vector<int> b1 = OddEvenSeparate1(a); e = clock(); cout << "time1:" << e - s << endl; cout << "first:" << endl; for (auto i : b1) { cout << i << " "; } cout << endl; // 第二种方法 s = clock(); list<int> 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所示。
图1 验证准确性
当输入数组为1000万时，debug下的速度如图2所示。
图2 release下速度对比
当输入数组为1000万时，release下的速度如图3所示。
图3 debug下速度对比
从上图可以看出，debug模式下自定义链表速度最快，但是release模式下vector速度最快，且自定义链表相对于STL中的list略快。
如果代码有什么需要改进的或者有什么bug，欢迎评论留言，我会及时更正以免误导他人~
如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！
