一个关于简单算法的疑问,请高手指导!(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--;
}
}
}
我自己也想了一个方法:很好理解,就是定义两个数组,第一个数组用于存贮原始数据,第二
个用于存贮排列后的数据。也定义两个指针,用于第二个
将一个无规律的整数数列重新排列,要求负数在前,非负在后。(时间尽可能最短)
老师的算法是(我的大概描述):定义一个数组存贮这一列数据,再定义两个指针,从两侧比较
。第一个指针从前面往后比较,判断是不是负,是则跳过,不是则不动;同时第二个指针从后
面往前比较,是正数则跳过,不是则不动;在出现第一个指针为正,第二个为负时,两者交换
,然后第一个指针加加,第二个指针减减。直到前一个指针比第二个指针小为止。
对应的代码如下:(以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次。