【演算法入門03】調整陣列順序使奇數位于偶數前面

核心考點：陣列操作，排序思想的擴展使用

輸入一個整數陣列，實作一個函式來調整該陣列中數字的順序，使得所有的奇數位于陣列的前半部分，所有的偶數位于陣列的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變，例如將陣列{1, 2, 3, 4, 5, 6}調整為{1, 3, 5, 2, 4, 6}，

決議一：（若相對位置可變）
若是題目當中沒有要求陣列調整后奇數和奇數，偶數和偶數的相對位置不變，那么我們可以使用兩個變數（left和right）來遍歷陣列，left從左往右尋找偶數，right從右往左尋找奇數，之后將left和right索引的元素進行交換，

如此進行下去，直到left和right錯開為止，

class Solution {
public:
	void reOrderArray(vector<int> &array) {
		size_t left = 0, right = array.size() - 1;
		while (left < right)
		{
			while (left < right&&array[left] % 2 == 1) //left向右找偶數
			{
				left++;
			}
			while (left < right&&array[right] % 2 == 0) //right向左找奇數
			{
				right--;
			}
			swap(array[left], array[right]); //交換left和right索引的元素
		}
	}
};

時間復雜度： O ( N ) O(N) O(N)?空間復雜度： O ( 1 ) O(1) O(1)

決議二：（空間換時間）
既然題目要求陣列調整后奇數和奇數，偶數和偶數的相對位置不變，那么我們可以使用一個輔助容器，先遍歷一遍原陣列，將陣列當中的奇數依次尾插到容器當中，

然后再遍歷一遍原陣列，將陣列當中的偶數也依次尾插到容器當中，

最后再將輔助容器當中的資料拷貝回原陣列即可，

class Solution {
public:
	void reOrderArray(vector<int> &array) {
		vector<int> temp; //輔助容器
		//遍歷陣列將奇數尾插到temp容器當中
		for (auto e : array)
		{
			if (e & 1) //是奇數
				temp.push_back(e);
		}
		//遍歷陣列將偶數尾插到temp容器當中
		for (auto e : array)
		{
			if (!(e & 1)) //是偶數
				temp.push_back(e);
		}
		array = temp; //將temp容器賦值給array容器
	}
};

時間復雜度： O ( N ) O(N) O(N)?空間復雜度： O ( N ) O(N) O(N)

決議三：（時間換空間）
我們也可以選擇將陣列原地進行調整，調整程序大致如下：
首先定義三個變數：

1. 變數 i：用于標記已經放好的奇數序列的后一個位置，
2. 變數 j：用于遍歷陣列，尋找奇數，
3. 變數 temp：用于暫時存盤變數 j 找到的奇數，

變數 j 從左向右依次遍歷陣列，尋找奇數，找到奇數后將其暫時存盤在temp變數當中，然后將變數 i 和變數 j 之間的數統一向后移動一位，最后再將temp變數當中存盤的奇數放到 i 的位置，之后記得更新 i 的位置（因為已經放好的奇數序列此時增加了一個），按此方法遍歷陣列，直到陣列被遍歷完畢為止，

動圖演示如下：

class Solution {
public:
	void reOrderArray(vector<int> &array) {
		int i = 0; //標記已經放好的奇數序列的后一個位置
		for (int j = 0; j < array.size(); j++)
		{
			if (array[j] & 1) //找到奇數
			{
				int temp = array[j]; //先將這個奇數存盤到temp變數當中
				//將變數i和變數j之間的數統一向后移動一位
				for (int k = j - 1; k >= i; k--)
				{
					array[k + 1] = array[k];
				}
				array[i] = temp; //將temp變數當中存盤的奇數放到i的位置
				i++; //更新i的位置
			}
		}
	}
};

時間復雜度： O ( N 2 ) O(N^2) O(N2)?空間復雜度： O ( 1 ) O(1) O(1)