数组操作

""""
借鉴快速排序的思想，时间复杂度O(n)，空间复杂度O(1)
"""

if __name__ == "__main__":
    a = list(map(int, input().strip().split()))
    i, j = 0, len(a) - 1
    while True:
        while i < len(a) and a[i] & 1 == 0: i += 1
        while j >= 0 and a[j] & 1 == 1: j -= 1
        if i >= j: break
        a[i], a[j] = a[j], a[i]
    print(' '.join(map(str, a)))

	

// 时间 O(n),空间O(1)
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int arr[maxn];
int n;

void partition() {
    int lo = -1;
    int cur = 0;
    while (cur < n) {
        if (~arr[cur] & 1) swap(arr[++lo], arr[cur]);
        ++cur;
    }    
}

int main() {
    while (scanf("%d", &arr[n]) == 1) ++n;
    partition();    

    for (int i = 0; i < n; ++i) 
        printf("%d%c", arr[i], (i == n - 1 ? '\n' : ' '));
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int x;
	vector<int> v1,v2;
	while(cin>>x)
	{
		if(x%2==0) v1.push_back(x);
		else	   v2.push_back(x);	
	}
	for(vector<int>::iterator it1=v1.begin();it1!=v1.end();it1++) cout<<*it1<<" ";
	for(vector<int>::iterator it2=v2.begin();it2!=v2.end();it2++) cout<<*it2<<" ";
	cout<<endl;
	return 0;	
} 

归并排序求解----时间复杂度（O(nlongn)）

实现原理与归并排序一样，代码如下：

#include <iostream>
(720)#include <vector>

using namespace std;

const int N = 1e6 + 10;

vector<int> arr;

void merge(vector<int> &nums,int l,int r)
    {
        if(l>=r) return ; //只有一个元素
        int mid=(l+r)>>1; //二分
        merge(nums,l,mid), merge(nums,mid+1,r); //计算左右两个区间中的逆序对
        int i=l,j=mid+1; //定义两个指针
        vector<int> temp;
        while(i<=mid&&j<=r) //归并
        {
            if(nums[i] % 2 == 0) temp.push_back(nums[i++]);
            else temp.push_back(nums[j++]); //后面的元素小于前面的元素素

        }
        //无论是i或者是j，元素都比之前的数组要大，所以不可能存在新的逆序，把数组填好就可以了
        while(i<=mid) temp.push_back(nums[i++]); 
        while(j<=r) temp.push_back(nums[j++]);
        i=l;
        for(auto x:temp) nums[i++]=x;
    }



int main()
{
    int x;
    while(cin >> x) {
        arr.push_back(x);
        if(cin.get() == '\n') break;
    }
    merge(arr, 0, arr.size() - 1);
    for (int j = 0; j < arr.size(); j ++ ) printf("%d ", arr[j]);

    return 0;
}

class Solution(object):
    def order(self):
        #获取输入的整数列表
        array = list(map(int,input().split(' ')))
         #用空间换取时间，建一个列表来保存结果
        res = []
        for i in array:
            #把偶数找出来放到res列表里
            if i%2==0:
                res.append(i)
        for i in array:
            #再把奇数找出来尾插到res列表里
            if i%2==1:
                res.append(i)
        print(" ".join(map(str,res)))
s = Solution()
s.order()

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    getline(cin,s);
    istringstream ss(s);
    vector<int> a,b;
    int x;
    while(ss>>x){
        if(x&1)
            b.push_back(x);
        else
            a.push_back(x);
    }
    int cnt = 1, n = a.size(), m = b.size();
    for(int i=0;i<n;i++){
        if(i==n+m)
            cout<<a[i]<<endl;
        else
            cout<<a[i]<<" ";
    }
    for(int i=0;i<m;i++){
        if(i==n+m)
            cout<<b[i]<<endl;
        else
            cout<<b[i]<<" ";
    }
    return 0;
} 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    vector<int>num,res1,res2;
    while(cin>>n)
        num.push_back(n);
    for(int i=0;i<num.size();i++)
    {
        if(num[i]%2==0)
            res1.push_back(num[i]);
        else
            res2.push_back(num[i]);
    }
    for(int i=0;i<res1.size();i++)
        cout<<res1[i]<<" ";
    for(int i=0;i<res2.size();i++)
        cout<<res2[i]<<" ";
    return 0;
}

n = map(int, raw_input().split())

a, b = [], []

for i in n :
    if i % 2 == 0 :
        a.append(i)
    else : b.append(i)
    pass

a += b

for i in a :
    print i, ;

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> arr;
    int t;
    while(cin>>t)
        arr.push_back(t);
    int i=0,j=arr.size()-1;
    while(i!=j){
        while(i<j&& !(arr[i]&1) )
            i++;
        while(i<j&& arr[j]&1)
            j--;
        swap(arr[i],arr[j]);
    }
    for(int k=0;k<arr.size();k++)
        cout<<arr[k]<<" ";
    return 0;
}

import java.util.Scanner;
public class Main {
	public static void Solution(int[] array) {
		if(array==null||array.length==0) return;
		int low = 0;
		int high = array.length-1;
		while(low<high) {
			while(low<high&&(array[low]&1)==0) {
				low++;
			}
			while(low<high&&(array[high]&1)==1) {
				high--;
			}
			if(low<high) {
				int temp = array[low];
				array[low] = array[high];
				array[high] = temp;
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		String[] strArray = str.split(" ");
		int[] intArray = new int[strArray.length];
		for(int i = 0;i<strArray.length;i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		Solution(intArray);
		for(int i = 0;i<intArray.length;i++) {
			System.out.print(intArray[i] + " ");
		}
	}
}

import java.util.Scanner;  public class Test01 { public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);  String line = scanner.nextLine();  String[] stringArray = line.split(" ");  int[] arr = new int[stringArray.length];  for(int i = 0;i < stringArray.length;i++) {
          arr[i] = Integer.parseInt(stringArray[i]);  } int low = 0;  int high = arr.length-1; while(low < high) { if(arr[low] % 2 == 0) {
                low++;  } if(arr[high] % 2 != 0) {
                high--;  } if(low < high) { int temp = arr[low];  arr[low] = arr[high];  arr[high] = temp;  }
     } for(int i = 0;i <arr.length;i++) {
          System.out.print(arr[i]);  System.out.print(" "); }
  }
}

arr=list(map(int,input().split()))
i=0
j=len(arr)-1
while i<j:
    if i<j and arr[i]%2==0:
        i+=1
    if i<j and arr[j]%2==1:
        j-=1
    if i<j:
        arr[i],arr[j]=arr[j],arr[i]
for i in range(len(arr)):
    print(arr[i],end=" ")
    

#include <stdio.h>
#include <stdlib.h>

const int N = 1E6;

void swap(int* a, int* b) {
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}

int main(const int argc, const char* const argv[]) {
  int nums[N], numsSize = 0;
  while (fscanf(stdin, "%d", nums + numsSize++) != EOF);  
  --numsSize;
  
  int l = 0, r = numsSize - 1;
  while (l < r) {
    while (l < r && !(*(nums + l) & 1)) ++l;
    while (l < r && *(nums + r) & 1) --r;
    if (l < r) swap(nums + l++, nums + r--);
  }
  
  int i;
  for (i = 0; i < numsSize; ++i)
    fprintf(stdout, "%d ", *(nums + i));
  
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <ll> odd;
vector<ll> even;
ll x;
int main(){
    while(scanf("%lld",&x)!=EOF){
        if(x&1) odd.push_back(x);
        else even.push_back(x);
    }
    even.insert(even.end(),odd.begin(),odd.end());
    for (auto iter = even.cbegin(); iter != even.cend(); iter++)
    { 
        if(iter==even.cbegin()) ;else cout<<" ";
        cout << (*iter);
    }
    cout<<endl;
    return 0;
}

def sortArray(arr):
    arr_even = []    # 分别保存偶数和奇数，append的时间复杂度是O(1),insert的时间复杂度是O(n)
    arr_odd = []

    for i in arr:
        if i % 2 == 0:
            arr_even.append(str(i))
        elif i % 2 == 1:
            arr_odd.append(str(i))

    arr_st = " ".join(arr_even+arr_odd)
    return arr_st

arr = map(int, input().strip().split(" "))
print(sortArray(arr))