注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

JavaScript将一个整数数组先按照因子数量排序,再按照数字大小排序

JavaScript 水墨上仙 1393次浏览 已收录 手机上查看

JavaScript将一个整数数组先按照因子数量排序,再按照数字大小排序
某笔试中的题,不得不承认这道题是个好题,考察了很多方面。js的数组操作,算法,逻辑能力,还有预防各种坑的能力……
一共搞了大概有4小时,函数逐个用firebug测,无法想象在考场上大概不到1小时,还不能调试……能写对的绝对是个神。公司遇到这样的神,就算其他题都不写也应该收了。
来源:http://blog.csdn.net/shirenfeigui/article/details/8072418

/*说明:将若干个正整数进行排序。排序方式为先按照因子数量从大到小排列,对于因子数量相同的按照值从大到小排。
比如数列[6,8,12,1,9,50],6的因子有1,2,3,6,因子数量为4;8的因子有1,2,4,8,因子数量为4.
按照因子数量排列的结果是[12,50,6,8,9,1]。对于因子相同的数比如12和50,按照从大到小排列,也就是说排列为50,12
需要注意的js的参数传递的特点:
1、可以在函数中直接改变它能够看到的变量和数组的值
2、数组的时可以通过传递进函数直接改变(类似于指针)
3、变量的值则不同,不能通过函数改变传入的值(和c语言相同)
总结一下里面的坑:
1、求因子数量。对于n=1的情况,只有一个因子。对于n是平方数的情况,平方数项是一个因子。除此以外的其他情况是两个因子
2、求因子数量里面是i<=Math.floor(Math.sqrt(n)),注意等号
3、del(arr,key)中,删除掉一个数字,要使指针前移一位 (此函数后来没有使用)
4、局部变量和全局变量的名字不要相同
*/
var a=[6,8,12,1,9,50,49,3,2,30];
showarray(a);
var sorted = new Array();
sortFactorValue();
showarray(a);
function sortFactorValue()//按照因子数量排列
{
	var f = new Array(a.length);
	getFactor(f);	//获取数字对应的因子数
	sortByFactor(f);  //获取一个因子数量从大到小的排列
}
function getFactor(f)	//获取每个数的因子数量
{
	for(var i=0;i<a.length;i++)
	{
		f[i]=countFactor(a[i]);
	}
	
}
function countFactor(n)	//获取数字n的因子数量
{
	if(n==1)
		return 1;
	var f=2;
	for(var i=2;i<=Math.floor(Math.sqrt(n));i++)
	{	if(n%i==0)
		{	if(Math.floor(Math.sqrt(n))==Math.sqrt(n))
			{	f+=1;}
			else
			{	f+=2;}
		}
	}
	return f;
}
function sortByFactor(f)	//按照因子值将因子序列和数列从大到小排列
{
	
	var i=0;
	while(i!=f.length)
	{	var start=i;
		var mf= Math.max.apply(Math,f.slice(i,f.length));
		i=findAndSwap(f,i,mf);	//对于数组f从第i位开始,找到因子数最大的数,将其交换到最前面,并且使i增加1。运行一次后最前面的若干个数都是待排序的因子最大数
		sortByValue(start,i);	//对于同因子数量的数字按值排列,排完之后i前面的数都是完成排序的数
	}
}
function findAndSwap(f,i,mf)	//从数组f的第i位开始,找到值为mf的数,将其交换到最前面,并且使i增加1
{
	for(var j=i;j<f.length;j++)
	{
		if(f[j]==mf)	//如果该数因子数量最大,将其换到最前面,并且让标志位i加1,i之前的所有数字已经是按factor排好的
		{
			if(j==i)	//如果该数就是第一个数,就不需要换了,直接移动指针
			{	i++;}
			else
			{	var p;	//如果该数不是第一个数,将它换到第一位,然后移动指针,进入下一循环比较后面的数列
				p=f[j];f[j]=f[i];f[i]=p;
				p=a[j];a[j]=a[i];a[i]=p;
				i++;
			}
		}
	}
	return i;
}
function sortByValue(s,e)  
//将数组a中从s开始到e为止的子数组进行排序
//这个函数的思路和findAndSwap是一致的,都是找到最大的数并将其换到第一位。如果数据结构足够合理,这两个函数应该可以合并
{
	while(s!=e)
	{
		var max=Math.max.apply(Math,a.slice(s,e));
		for(var i=s;i<e;i++)
		{
			if(a[i]==max)
			{
				if(i==s)
				{	s++;}
				else
				{
					var p;
					p=a[i];a[i]=a[s];a[s]=p;
					s++;
				}
			}
		}
	}
}
/*function factorList(f)	//获取该数列因数个数从大到小的排列
//开始的想法是先找到因子序列然后再遍历一次数组,后来发现重复遍历了,太麻烦
{
	var fl = new Array();
	var t = new Array();
	t = t.concat(f);
	while(t.length)
	{	
		var mf= Math.max.apply(Math,t);
		
		fl.push(mf); //将最多因子数放入数组
		del(t,mf);	//将最多因子的数从数组中删掉
	} 
	return fl;
}*/
function del(arr,key)	//从数组a中删除值为key的所有数字,注意变量名不能和公有变量相同
{	
	for(var i=0;i<arr.length;i++)
	{	
		if(arr[i]==key)
		{	arr.splice(i,1);	//因为删掉了一个数,所以位置要往前移动一个
			i--;
		}
	}
}
function showarray(a0)  //输出数组
{
	for(var i=0;i<a0.length;i++)
	{
		document.write(a0[i]+" ");
	}
	document.write("</br>");
}


喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……