如何根据不完整的标准进行排序？

Question

首先，我尝试将自己的函数传递给Array.sort，但排序不正确。注意结果中的'c'before'a'是如何出现的，即使案例if (b == 'a' && a == 'c')处理正确。这些数据只是举例。我的实际数据不按字母顺序排序。它必须使用a_before_b和b_before_a函数中说明的逻辑。由于我只有确定某些（不是全部）元素对的相对顺序的条件，因此可能存在多个有效的元素顺序。我只需要生成任何有效的顺序，其中有效的方式不与我的任何条件（在a_before_b和b_before_a函数中定义）相矛盾。const sorted = ['a', 'b', 'c', 'd']; // I do NOT have access to thisconst 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;}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)); // [ 'c', 'a', 'd', 'b' ]然后我尝试从头开始编写自己的排序。但是进入了死循环，不知道为什么。const sorted = ['a', 'b', 'c', 'd'];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;}const b_before_a = (a, b) => {  if (b == 'a' && a == 'c') return true;  if (b == 'b' && a == 'c') return true;}const findAnUnsortedElement = array => {  for (let [i, element] of Object.entries(array)) {    i = +i;    const a = element;    const b = array[i + 1];    if (b === undefined) return 'SORTING_COMPLETE';    if (!a_before_b(a, b)) console.log(a, 'should not be before', b);    if (b_before_a(a, b)) console.log(b, 'should be before', a);    if (!a_before_b(a, b) || b_before_a(a, b)) return a;  }}// from w3schoolsfunction move(arr, old_index, new_index) {  while (old_index < 0) {    old_index += arr.length;  }  while (new_index < 0) {    new_index += arr.length;  }  if (new_index >= arr.length) {    var k = new_index - arr.length;    while ((k--) + 1) {      arr.push(undefined);    }  }  arr.splice(new_index, 0, arr.splice(old_index, 1)[0]);  return arr;}

Answer 1

const unsorted = ['c', 'd', 'a', 'b'];
const sorted = unsorted.sort();

它应该工作 我不确定你的问题是什么。

Answer 2

我之前给出的答案中的算法（您（首先）接受了该算法）实际上是基于启发式算法。

为了保证排序后的输出没有任何违规，您可以将此问题视为图形问题。只要两个值可以进行比较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));

Answer 3

也许是这样的

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));