javascript - JS中的递归排序

Question

我在面试中被要求编写一个程序/算法来使用递归对数字数组进行排序。

虽然我含糊地回答了它，但我尝试并想出了以下代码:

您可以使用以下 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 压入数组并返回。
• 否则，
  • 对于数字和字符串检查相等性并返回正确的顺序。
  • 对于其他任何事情，返回相同的值

---

问题是，是否有更好的实现方式(算法明智)？

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

我也知道，目前的代码不支持:

• 排序。它只会升序排序。
• 可能会中断日期对象，并且通常不支持对象。

谢谢!

Answer 1

我认为大多数面试官都希望您回复 quicksort或 merge sort (或两者)给出这个问题。在这两者中，快速排序更容易记住并在紧要关头重新创建，因为合并排序的合并步骤很容易搞砸。

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(', '))