javascript-JS中的递归排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了javascript-JS中的递归排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2832字,纯文字阅读大概需要5分钟。
内容图文
在一次采访中,我被要求编写一个程序/算法,以使用递归对数字数组进行排序.
尽管我隐约回答了它,但我尝试并提出了以下代码:
您可以使用下面的JSFiddle链接进行游戏.
function sort(arr) {
if (arr.length === 2) {
const v1 = arr[0];
const v2 = arr[1];
const isGreater = (
(isString(v1) && isString(v2) && v1.toString().toLocaleCompare(v2) > 0) ||
(isNumber(v1) && isNumber(v2) && v1 > v2)
);
return isGreater ? [ v2, v1 ] : [ v1, v2 ];
} else {
const last = arr.pop();
const ret = sort(arr);
const newLast = ret.peekLast();
if (newLast < last) {
return [ ...ret, last ];
} else {
return sort( [ last, ...ret ] );
}
}
}
function isString(value) { return typeof value === 'string'; }
function isNumber(value) { return Number.isFinite(value); }
Array.prototype.peekLast = function () { return this.slice().pop(); }
//console.log(sort([1,2,3,4,5]))
console.log(sort([5,4,3,2,1]))
我实现的算法是:
>取阵列并检查其长度是否大于2.
>如果是,
>删除最后一个元素并将其存储在变量中.
>再次调用没有最后一个元素的相同函数,直到有2个项目.
>接受从递归调用返回的数组,并查看最后一个元素.
>如果newLast值大于previousLast
>将previousLast推为第一个元素,然后再次使用此数组调用自身.
>否则,将previousLast推入数组并返回它.
>其他
>对于数字和字符串,请检查是否相等并返回正确的顺序.
>对于其他内容,返回相同的值
问题是,是否有更好的实施方法(明智的选择)?
注意:我不希望代码有所改进.这个问题的目的是改进算法部分或我错过的任何常规内容.
我也知道,当前代码不支持:
>排序顺序.它将仅按升序排序.
>对于日期对象可能会中断,并且通常不支持对象.
谢谢!
解决方法:
我看到中间价值创造的脉络并非无关紧要.
> peekLast调用Array.prototype.slice,它复制数组.您复制整个数组只是为了返回最后一个元素.
Array.prototype.peekLast = function () { return this.slice().pop(); }
Array.prototype.peekLast = function () { return this[this.length]; }
每次无需复制即可获得相同的结果.
>在[… arr,x]之类的表达式中使用传播参数会完全复制arr.
arr.concat([x])做同样的事情而没有复制(或突变)arr
您调用peekLast并在输入中每个元素使用一次… x.仅对这些操作,仅对100个项目的列表进行调用sort就将复制10,000多个元素.仅1,000个项目的列表将复制超过1,000,000个元素.算法改进的空间?当然.
马克·迈耶(Mark Meyer)从右脚开始.如果要使用递归,最好以函数样式编写程序,因为它将产生最佳结果.将命令式(陈述,突变,重新分配,其他副作用等)与递归混合在一起是偏头痛的秘诀.
Mark的算法,无论“代码改进”多么出色,您的问题都要求“算法改进”.在这种情况下,Mark的算法由于使用许多… x表达式而遭受类似的中间值创建.
另一个潜伏的罪行是在同一数组rest上重复使用.filter.这将导致效率低下的过程,因为每个元素将其完全迭代其余两(2)次.这是达到低挂起的内置函数的征兆,这些函数确实接近您想要的功能,但不完全符合您想要的功能.一个更好的函数将遍历数组一次并返回两个结果.
由于代码质量的显着提高,Mark程序的效率低下是可以原谅的.他的程序比您的程序更具可读性,因为他使用的是函数样式,而这正是递归的来源.低效率也很容易解决,所以也许这对您来说是一个练习?
让我们看看这是否能使您的大脑运转.在让您窒息的过多信息之前,我们将看看别人提交的答案.
内容总结
以上是互联网集市为您收集整理的javascript-JS中的递归排序全部内容,希望文章能够帮你解决javascript-JS中的递归排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。