一个关于简单算法的疑问,请高手指导!(c语言 )

来源:百度知道 编辑:UC知道 时间:2024/06/05 14:55:16
原题如下:

将一个无规律的整数数列重新排列,要求负数在前,非负在后。(时间尽可能最短)

老师的算法是(我的大概描述):定义一个数组存贮这一列数据,再定义两个指针,从两侧比较

。第一个指针从前面往后比较,判断是不是负,是则跳过,不是则不动;同时第二个指针从后

面往前比较,是正数则跳过,不是则不动;在出现第一个指针为正,第二个为负时,两者交换

,然后第一个指针加加,第二个指针减减。直到前一个指针比第二个指针小为止。

对应的代码如下:(以C语言为平台)

void pass(int a[],int n)

{

int i,j,t; // 定义两个变量i,j做为指针,t为对调时的中间变量。

i=1;j=n; // 这里的数组下标假设从1开始至n结束。

while(i<j) // 循环终止条件。

{

while((a[i]<0) && (i<j)) i++; //i往后移,直至指向正数。

while((a[j]>0)&&(i<j)) j--; //j往前移,直至指向负数。

if(i<j)

{ //下面是对换.

t=a[i];

a[i]=a[j];

a[j]=t;

i++;

j--;

}

}

}

我自己也想了一个方法:很好理解,就是定义两个数组,第一个数组用于存贮原始数据,第二

个用于存贮排列后的数据。也定义两个指针,用于第二个

不是这样的
运行时消耗的时间主要在赋值上,而非比较,你会有n次赋值,而老师的会有3n/4次(期望值)赋值,比你少一些,所以快。

关于3n/4的解释:
每次交换要3次赋值,是随机数据的话,平均交换n/4次,所以...

你的算法也有好处,就是稳定性
你的无论什么数据都是n次,而老师的最少0次,最多3n/2次。