3 回答

TA貢獻1843條經驗 獲得超7個贊
const unsorted = ['c', 'd', 'a', 'b']; const sorted = unsorted.sort();
它應該工作 我不確定你的問題是什么。

TA貢獻2080條經驗 獲得超4個贊
我之前給出的答案中的算法(您(首先)接受了該算法)實際上是基于啟發式算法。
為了保證排序后的輸出沒有任何違規,您可以將此問題視為圖形問題。只要兩個值可以進行比較true(使用任一比較器函數),那么該對就代表圖中的一條邊。
如果順序一致,那么一定有一個值是其他值中最小的,否則就會有一個循環。
因此,有了這些知識,我們就可以為圖中的每個節點確定到這樣一個最小節點的最長路徑有多長。當您找到到此類最小節點的最長距離時,您可以使用該路徑的長度作為絕對順序指示。
這是一個實現:
class Node {
constructor(value) {
this.value = value;
this.prev = new Set;
this.order = 0; // No order yet
}
orderWith(other) {
if (other === this) return;
if (a_before_b(this.value, other.value) || b_before_a(other.value, this.value)) {
other.prev.add(this);
} else if (a_before_b(other.value, this.value) || b_before_a(this.value, other.value)) {
this.prev.add(other);
}
}
setOrder(path = new Set) {
// Use recursion to find length of longest path to "least" node.
if (this.order) return; // already done
if (path.has(this)) throw "cycle detected";
let order = 1;
for (let prev of this.prev) {
prev.setOrder(path.add(this));
order = Math.max(order, prev.order + 1);
}
this.order = order; // If order is 1, it is a "least" node
}
}
const a_before_b = (a, b) => {
if (a == 'a' && b == 'd') return true;
if (a == 'b' && b == 'c') return true;
}
const b_before_a = (a, b) => {
if (b == 'a' && a == 'c') return true;
if (b == 'b' && a == 'c') return true;
}
function mySort(arr) {
// Create a graph: first the nodes
let nodes = {}; // keyed by values in arr
for (let value of arr) nodes[value] = nodes[value] || new Node(value);
// Then the edges...
for (let i = 0; i < arr.length; i++) {
for (let j = i+1; j < arr.length; j++) {
nodes[arr[i]].orderWith(nodes[arr[j]]);
}
}
// Set absolute order, using the longest path from a node to a "least" node.
for (let node of Object.values(nodes)) node.setOrder();
// Sort array by order:
return arr.sort((a, b) => nodes[a].order - nodes[b].order);
}
const sorted = ['a', 'b', 'c', 'd'];
const unsorted = ['c', 'd', 'a', 'b'];
console.log(mySort(unsorted));

TA貢獻1863條經驗 獲得超2個贊
也許是這樣的
const sorted = ['a', 'b', 'c', 'd']; // I do NOT have access to this
const unsorted = ['c', 'd', 'a', 'b'];
const a_before_b = (a, b) => {
if (a == 'a' && b == 'd') return true;
if (a == 'b' && b == 'c') return true;
if (a == 'a' && b == 'c') return true;
}
const b_before_a = (a, b) => {
if (b == 'a' && a == 'c') return true;
if (b == 'b' && a == 'c') return true;
}
const mySortingFunction = (a, b) => {
if (a_before_b(a, b)) return -1;
if (b_before_a(a, b)) return 1;
return 0;
}
// doesn't produce correct sorting
console.log(unsorted.sort(mySortingFunction));
添加回答
舉報