编程论坛 → C++教室

[求助]做个算法题

chenkuanyi 发布于 2007-05-18 22:27， 585 次点击

编写一个函数实现将数组中>=0的数组元素排列在数组前部，而将<0的数组元素排列在数组后部，并满足以下要求：
（1）不要对数组元素进行排序，只需要满足归类要求即可
（2）尽可能降低算法复杂度
（3）数组元素只能在数组内部进行移动、交换等操作（可借用临时变量），但不能使用另外定义的数组变量

我是在数组头尾各定义一个指针，当前面的指针<0,后面的指针>0时就交换，
但实现时有错，请大家给我改一下啊，照我的算法思路；

# include <iostream>
using namespace std;

void main()
{
int a[] = {1, 3, -7, -4, 4, 8, -5, 33, 55, -6};
int *p = NULL;
int *q = &a[9];

for ( p = &a[0]; p != q; p++)
{
if ((*p) < 0)
{
while (p != q)
{
if ( *q > 0)
{
int temp = 0;
temp = *p;
*p = *q;
*q = temp;
q--;
break;
}
else
{
q--;
}
}
}
}
for (int i = 0; i < 10; i++)
{
cout << a[i] << "\t";
}
system("pause");
}

这时有时正确的：
E:\>11
1 3 55 33 4 8 -5 -4 -7 -6

但当我改变数组时，有时会有系统计错误，

[此贴子已经被作者于2007-5-18 22:36:48编辑过]

9 回复

#2

Ｉ喜欢c2007-05-18 23:04

# include <iostream>
using namespace std;

int main()
{
int a[] = {1, 3, -7, -4, 4, 8, -5, 33, 55, -6};
int t,i,n;
n=sizeof(a)/sizeof(int);
for(i=0;i<n;i++)
if(a[i]<0)
{
t=a[i];a[i]=a[n-1];a[n-1]=t;
n--;i--;
}
for (int i = 0; i < sizeof(a)/sizeof(int); i++)
{
cout << a[i] << endl;
}
getchar();

}

#3

aipb20072007-05-19 01:02

其实楼主你的方法，我认为是效率不错的选择了。
不过你何必用指针去迭代，用个索引不就OK了！？

#4

chenkuanyi2007-05-19 09:39

谢谢啊，
大家能指出我的那个算法错在那里吗？
照着我的步骤改一改把
谢谢啊

#5

aipb20072007-05-19 10:09

以下是引用chenkuanyi在2007-5-19 9:39:46的发言：

谢谢啊，
大家能指出我的那个算法错在那里吗？
照着我的步骤改一改把
谢谢啊

第一个循环条件那里不应该是!=而是<=。

当两个指针相邻且需要交换时，自增，自减会使指针交叉，达不到相等。
再来就出现内存错误了。

这就是为什么有时行有时不行！

[此贴子已经被作者于2007-5-19 10:11:17编辑过]

#6

leeco2007-05-20 01:38

这是语言题……不是算法题

#7

rtx792007-05-20 22:00

怎的这么巧，我在看的书正好是这个quicksort法（快速排序法）

#8

aipb20072007-05-20 22:19

以下是引用rtx79在2007-5-20 22:00:24的发言：
怎的这么巧，我在看的书正好是这个quicksort法（快速排序法）

对啊，quicksort用了这个分割思想！

#9

孤魂居士2007-05-22 01:41

我支持6楼的意见

#10

hejinjiang2007-05-22 09:08

题目要求让编写一个函数..2楼写得不是函数啊..

1