代码之家 › 专栏 › 技术社区 › Rajesh Rahul

JS中的递归排序

algorithm javascript

Rajesh Rahul · 技术社区 · 7 年前

我在一次采访中被要求写一个程序/算法,用递归对一个数字数组进行排序。

虽然我含糊其辞地回答了这个问题,但我还是试着想出了以下代码:

你可以用下列方法 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个项为止。
- 从递归调用返回的accept数组,并查看最后一个元素。
- 如果 newLast 值大于 previousLast
  - 推 最后的最后 作为第一个元素,然后使用此数组再次调用自身。
- 如果不是,推 最后的最后 数组并返回它。
否则,
- 对于数字和字符串,请检查相等性并返回正确的顺序。
- 对于其他任何内容,返回相同的值

问题是,有没有更好的方法来实施( 藻类智慧 )?

注: 我不期望代码改进。这个问题的目标是改进算法部分或任何我遗漏的一般性内容。

我也知道,当前代码不支持:

排序顺序。它将只按升序排序。
日期对象可能中断,一般不支持对象。

谢谢!

3 回复 | 直到 7 年前

Mulan 7 年前

我看到了一种中间价值创造的脉络,它不是无关紧要的。

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

你打电话 皮克斯特 和使用 ...x 输入中每个元素一次。打电话 sort 在一个只有100个项目的列表中,将复制超过10000个元素,仅用于这些操作。只有1000个项目的列表将复制超过1000000个元素。算法改进的空间?当然。

马克·迈耶用右脚开始你的动作。如果要使用递归,最好用函数样式编写程序,因为它将产生最佳结果。将命令式(语句、突变、重新分配、其他副作用等)与递归混合是偏头痛的秘诀。

马克的算法,无论多么伟大 “代码改进” 你的问题是 “算法改进” . 在这种情况下,Mark的算法由于使用了大量的 …X 表达。

另一个潜伏的进攻是 .filter 在同一阵列上, rest . 这会创建一个效率低下的过程,因为它完全迭代 休息 每个元件两(2)次 .这是达到低悬挂内置功能的症状关闭为了你想要的,但不是 确切地 你想要什么。更好的函数将遍历数组一旦并返回 二者都 结果。

由于代码质量的显著提高,Mark程序中的效率低下基本上是可以原谅的。他的程序比你的程序可读得多,因为他使用的是函数样式,这就是递归的来源。效率低下也很容易解决,所以这对你来说可能是一个练习?

让我们看看这是否能让你的大脑活跃起来。我们会看到其他人在用太多信息压制你之前提交了什么答案。

Mark 7 年前

我想大多数面试官都希望你能回答 quicksort 或 merge sort (或两者)给出了这个问题。其中,QuickSort在紧要关头更容易记住和重新创建,因为合并排序的合并步骤很容易弄乱。

Quicksort是一个非常漂亮的算法,很自然地适合于JavaScript的功能工具。如果你要去面试的话,真的很值得理解:

const arr = [6, 1, 5, 3, 9, 6, 7, 10, 16, 4, 0, 12, 2]

function qsort(arr){
    if (arr.length < 2) return arr
    // choose a pivot, p
    // the choice of pivot can effect worst-case performance
    // for this, we'll just use the first element.
    const [p, ...rest] = arr

    // partition array into element greater and lesser that the pivot
    // this can be optimized so you don't loop through the array twice
    const low  = rest.filter(n => n <= p)
    const high = rest.filter(n => n > p)

    // recurse on both partitions and reassemble as recursion unwinds
    return [...qsort(low), p, ...qsort(high)]
}
console.log(qsort(arr).join(', '))

Hiteshdua1 7 年前

如果因为这一行有重复的元素,您的代码将失败。 if (newLast < last) {

它将进入无限递归

使用作为输入传递的重复数组引用代码段

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();
    debugger;
    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([3,3,5,2]))