奇偶排序-在线编程-K6K4.com

给定一个随机整数序列，请调整数字的顺序，使得所有的奇数排在偶数前面，且奇数之间的原有顺序不变，偶数之间的原有顺序也不变。
要求：时间复杂度O(n)

输入、输出描述

输入：

arr: 随机整数数组
n: 数组长度

输出：

排好序的数组

Example

输入：

arr=[3,1,6,2,9,4,7]
n=7

输出：

[3,1,9,7,6,2,4]

代码：

import java.util.*;

public class Main {

 

 public int[] solution2(int[] arr,int n) {

   int[] a = new int[n];
   int j = 0;
   for(int i=0;i<n;i++){
     if(arr[i] % 2 == 1){
     	a[j++] = arr[i];
     }   
   }
	for(int i=0;i<n;i++){
     if(arr[i] % 2 == 0){
     	a[j++] = arr[i];
     }   
   }


        return a;
    }
  
  public int[] solution(int[] arr,int n) {

   int i,j,k;
	if(n<=0){

		return arr;
	}
	if (arr[0] % 2 == 1)
	{
		j = 0;
		while (j<n && arr[j] % 2 == 1)
		{
			j++;
		}
		if (j == n)
		{
			return arr;
		}
		k = j;
		while (k<n && arr[k] % 2 == 0)
		{
			k++;
		}
		if (k == n)
		{
			return arr;
		}
		//偶数后的第一个奇数
		int t = arr[k];

		i = k-1;
		while (i>=0 && arr[i]%2==0)
		{
			arr[i+1] = arr[i];
			i--;
		}
		arr[i+1] = t;

		k++;
		while (k<n)
		{
			if (arr[k] %2 ==0)
			{
				k++;
			}
			else
			{
				t = arr[k];
				i = k-1;
				while (i>=0 && arr[i]%2==0)
				{
					arr[i+1] = arr[i];
					i--;
				}
				arr[i+1] = t;
				k++;
			}
		}
	}
	else
	{
		//2,3,4,5,6,7,8
		k = 0;
		while (k<n && arr[k] % 2 == 0)
		{
			k++;
		}
		if (k==n)
		{
			return arr;
		}
		//偶数后的第一个奇数
		int t = arr[k];

		i = k-1;
		while (i>=0 && arr[i]%2==0)
		{
			arr[i+1] = arr[i];
			i--;
		}
		//插入到首位
		arr[i+1] = t;

		k++;
		while (k<n)
		{
			if (arr[k] %2 ==0)
			{
				k++;
			}
			else
			{
				t = arr[k];
				i = k-1;
				while (i>=0 && arr[i]%2==0)
				{
					arr[i+1] = arr[i];
					i--;
				}
				arr[i+1] = t;
				k++;
			}
		}
	}
    return arr;
    }
}