首页 > 试题广场 >

在一个N个整数数组里面,有多个奇数和偶数,设计一个排序算法,

[问答题]
在一个N个整数数组里面,有多个奇数和偶数,设计一个排序算法,令所有的奇数都在左边。
请完成sort的代码实现(C++或Java)
C++:
void sort(int N, int[]a)
{
    …
}

Java:
void sort(int[]a)
{
    …
}
例如: 当输入a = {8,4,1,6,7,4,9,6,4},
a = {1,7,9,8,4,6,4,6,4}为一种满足条件的排序结果
推荐
Ian头像 Ian
这题要求的排序仅仅需要奇数在左边,还不要求有序,那么复杂度可以降到O(n),算法也十分简单。遍历数组,遇到奇数就把它放到左边。
C++:
void sort(int N, int a[])
{
 int l_cnt = 0, temp;
    // l_cnt记录奇数已经有几个奇数
 for(int i = 0; i < N; i++) {
 if (a[i] % 2) {
 temp = a[l_cnt];
 a[l_cnt] = a[i];
 a[i] = temp;
 l_cnt++;
 }
 }
}
Java类似。

编辑于 2015-01-07 20:47:38 回复(1)
C++
从数组的左右两边开始往中间扫,左边遇到偶且右边遇到奇,则左右调换,若一边遇到奇或偶则继续往前走,知道左右相遇结束。最差时间复杂度O(N),最好在O(N/2)能完成
void sort(int N, int a[])
{
    int left = 0;
    int right = N-1;
    int tmp = 0;
    while(left < right)
    {
        if(a[left]%2 == 0 && a[right]%2 == 1)
        {
            tmp = a[left];
            a[left] = a[right];
            a[right] = tmp;
            left ++;
            right --;
        }
        else if(a[left]%2 == 0 && a[right] %2 ==0)
        {
            right --;
        }
        else if(a[left]%2 == 1 && a[right] %2 == 1)
        {
            left ++;
        }
        else
        {
            left ++;
            right --;
        }
    }
}
发表于 2015-01-11 02:23:02 回复(0)
void sort(int N, int[]a)
{
    int *s=a;int *s=a;
    int *l=a+N;
    for(;s<l;s++){
        if(!(*s&1)){
            for(;s<l;l--){
                if(*l&1){
                    int temp=*l;
                    *l=*s;
                    *s=temp;
                    break;
                }
            }
        }
    }
}

发表于 2015-01-07 14:08:23 回复(1)
function sortNewArr(arr){
    var leftArr = [];
    var rightArr = [];
    for(var i in arr){
        if(arr[i] % 2 === 1){
            leftArr.push(arr[i]);
        }else{
            rightArr.push(arr[i]);
        }
    }
    console.log(leftArr.concat(rightArr));
}
sortNewArr([3,6,8,7,9,10,5,1,2,4]);

发表于 2017-09-18 13:42:00 回复(0)
代码如下 #include "stdafx.h"
#include <iostream>
using namespace std;

int *sort(int*a, int n){
	int* b = new int[n];
	int j = 0;
	int count = 0;
	for (int i = 0; i < n; i++){
		if (a[i] % 2 >0){
			b[n - 1 - count] = a[i];
			count++;
		}
		else{
			b[j] = a[i];
			j++;
		}
	}
	return b;
}
int _tmain(int argc, _TCHAR* argv[])
{
	//int a[6] = { 1,3,5,6,8,7};
	int n;
	cout << "请输入数组中数字的个数" << endl;
	cin >> n;
	int *a;
	a = new int[n];
	cout << "请输入任意一串数字类似(1 3 5 6 8 7)" << endl;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	int *b = new int[n];
	b=sort(a, n);
	for (int i = 0; i < n; i++){
		cout << b[i]<<" ";
	}
	return 0;
} 


发表于 2017-03-04 21:52:07 回复(0)
public void sort(int [] a) {
    int s = 0;
    int e = a.length - 1;
    int t;
    while (s < e) {
        while ((s < e) && (a[s]&1) == 1) // 如果是奇数则继续找
            s++;
        while ((s <  e) && (array[e]&1) == 0) // 如果是偶数则继续找
            e--;
        if(s < e) {
            t = a[e];
            a[e] = a[s++];
            a[e--] = t;
        }
    }
}
发表于 2016-09-20 23:23:00 回复(0)
void swap(int &a,int &b){
    int tmp;
    tmp=a;
    a=b;
    b=tmp;
}

void sort(int n,int a[]){
    int i=0,j=n-1;
    while(i<j){
        if((a[i]&1)==0 && (a[j]&1)==1){
            swap(a[i],a[j]);
            i++;
            j--;
        }
        else if((a[i]&1)==0 && (a[j]&1)==0)
            i++;
        else if((a[i]&1)==1 && (a[j]&1)==1)
            j--;
        else{
            i++;
            j--;
        }
    }
}
发表于 2015-04-28 14:54:00 回复(0)
#include <iostream>
using namespace std;
void Grial(int a[],int n)
{
    int j=0;
    int i=j-1;
    int temp;
        while(j<n)
    {
        while(j<n-1 && a[j]%2==0)j++;
        i++;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        j++;
    }
}
int main()
{
    int a[]={1,2,3,5,856,74,34,5,32,4};
    Grial(a,10);
    for(int i=0;i<10;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
发表于 2015-04-28 00:00:47 回复(0)
void sort(int N, int A[]) {
    int odd = 0, even = N - 1;
    for (int i = 0; i < N;) {
        if (A[i] & 1 && odd < i) {
            swap(A[i], A[odd++]);
        } else if ((A[i] & 1) == 0 && even > i){
            swap(A[i], A[even--]);
        } else {
            ++i;
        }
    }
}


发表于 2015-04-02 10:14:22 回复(0)
其实这道题可以利用快速排序算法思想来实现的 但是好像有大小限制所以还是采用了比较蠢的方法。

设置大小一样的数组B[N],将a[N]赋值给b[],之后历边a[];如果是奇数,就放在a[]中,偶数最后再放进来;代码如下:
C++
void sort(int N ,int[] a){
int b[N];
int i=0,j=0;
for(i=0;i<N;i++){
b[i] = a[i];
}
for(i=0,j=0;i<N;i++){

if(b[i]%2==1){
a[j] = b[i];
j++;
}
}
for(i=0;i<N;i++){
if(b[i]%2!=1){
a[j]=b[i];
j++;
}
}


}
发表于 2014-12-29 17:42:35 回复(0)