为什么我的排序算法无法正确排序? [英] Why is my sorting algorithm not sorting correctly?

问题描述

为我发布的问题的最佳答案，我得到了此排序功能.它适用于示例数据，但似乎不适用于我的实际数据，我不确定为什么.

I was given this sorting function in the best answer to a question I posted. It worked on the example data, but does not appear to work on my actual data and I am not sure why.

我的数据可以在这里查看: JSON

My data can be see here: JSON

它是这样的对象的对象:

It's an object of objects like this:

"Montana": {
    "superiors": [
      "Massachusetts",
      "Oklahoma",
      "New Mexico"
    ],
    "inferiors": [
      "North Carolina"
    ]
  }

用于指示排序功能.在此，列表中的 Montana 必须高于 North Carolina .但是在 Massachusetts ， Oklahoma 和 New Mexico 下(顺便说一下，这与地理无关).

It exists to instruct the sorting function. Here, Montana must be higher up in the list than North Carolina. But below Massachusetts, Oklahoma, and New Mexico (nothing to do with geography by the way).

• 这与对象键的顺序无关.

但是排序并没有被精确地遵循(尽管大多数情况下都被遵循).例如， states ['North Carolina'].superiors.includes('Ohio')=== true 那么为什么'Ohio'列在'North下卡罗来纳州的?

But the sorting isn't being followed precisely (it's mostly followed though). For example, states['North Carolina'].superiors.includes('Ohio') === true so why is 'Ohio' listed beneath 'North Carolina'?

  fetch('https://api.npoint.io/7571e85ef470a2a7f189')
    .then(data => data.json())
    .then(states => {
      function mySort(arr) {
        const scores = Array(arr.length).fill(0);
        for (let i = 0; i < arr.length; i++) {
          for (let j = 0; j < arr.length; j++) {
            if (i === j) continue;
            const a = arr[i];
            const b = arr[j];
            if (states[a].inferiors.includes(b) || states[b].superiors.includes(a)) scores[j]++;
            else if (states[b].inferiors.includes(a) || states[a].superiors.includes(b)) scores[i]++;
          }
        }
        // Sort arr by scores:
        return arr.map((val, i) => [scores[i], val])
          .sort((a, b) => a[0] - b[0])
          .map(pair => pair[1]);
      }

      const names = Object.keys(states);

      console.log(mySort(names));

      /*
      [
        'Tennessee',     'Oklahoma',             'Alaska',
        'Wisconsin',     'Arkansas',             'New York',
        'Nevada',        'Montana',              'Georgia',
        'Massachusetts', 'Hawaii',               'Connecticut',
        'California',    'Kansas',               'Utah',
        'North Dakota',  'New Mexico',           'Nebraska',
        'Pennsylvania',  'Louisiana',            'New Jersey',
        'Arizona',       'Colorado',             'Maryland',
        'Oregon',        'Missouri',             'Virginia',
        'Rhode Island',  'Mississippi',          'South Carolina',
        'Illinois',      'Texas',                'Florida',
        'Washington',    'District of Columbia', 'Kentucky',
        'Minnesota',     'Iowa',                 'Alabama',
        'New Hampshire', 'Idaho',                'South Dakota',
        'Indiana',       'Michigan',             'North Carolina',
        'Ohio'
      ]
      */
      // states['North Carolina'].superiors.includes('Ohio') === true
      // so why is 'Ohio' listed beneath 'North Carolina'?
    });

这是JSON数据，以防我的链接中的数据遭到破坏:

Here is the JSON data in case the data in my link gets vandalized:

{"Iowa":{"inferiors":[],"superiors":["Alaska","Oklahoma","California","Hawaii","New Jersey","Virginia","Florida","Washington","Minnesota","Texas","Idaho","Alabama","Ohio"]},"Ohio":{"inferiors":["North Carolina","Michigan","Iowa","New Hampshire"],"superiors":["New York","California","Arizona","Illinois","Texas","Pennsylvania","Florida","Indiana","Tennessee","Massachusetts","Washington","Colorado","District of Columbia","Maryland","Kentucky","Oregon","Oklahoma","Wisconsin","Nevada","New Mexico","Missouri","Virginia","Georgia","Nebraska","Minnesota","Louisiana","Hawaii","Alaska","New Jersey","Idaho","Alabama","Arkansas","Utah","Rhode Island","Mississippi","South Carolina","Connecticut","Montana","Kansas","North Dakota","South Dakota"]},"Utah":{"inferiors":["Idaho","South Dakota","Ohio","Michigan"],"superiors":["New York"]},"Idaho":{"inferiors":["Ohio","Iowa","South Dakota","Michigan","North Carolina"],"superiors":["Alaska","Oklahoma","California","Hawaii","Minnesota","New Jersey","Virginia","Florida","Washington","Texas","New York","Louisiana","Illinois","Arkansas","Utah","Rhode Island","Mississippi","Maryland","Nebraska","District of Columbia","Kentucky","Connecticut"]},"Texas":{"inferiors":["North Carolina","Michigan","Ohio","Indiana","Idaho","Alabama","Iowa"],"superiors":["New York","California","Tennessee","Massachusetts","Oklahoma","Wisconsin","Nevada","New Mexico","Alaska","Hawaii"]},"Alaska":{"inferiors":["California","Hawaii","New Jersey","Virginia","Florida","Washington","Minnesota","Texas","Idaho","Alabama","Ohio","Iowa","New Mexico","Mississippi","Rhode Island","North Dakota","South Carolina","District of Columbia","Colorado","Arizona","Kentucky","New Hampshire","Oregon","Nebraska","Illinois","Indiana","South Dakota","North Carolina"],"superiors":["Tennessee"]},"Hawaii":{"inferiors":["Minnesota","Kentucky","Washington","Pennsylvania","Illinois","Georgia","Maryland","Ohio","New Jersey","Virginia","Florida","Texas","Idaho","Alabama","Iowa","Mississippi","Rhode Island","North Dakota","South Carolina","District of Columbia","Colorado","Arizona","New Hampshire","Missouri","Utah","Louisiana","Michigan"],"superiors":["New York","Tennessee","Oklahoma","Alaska","Nevada"]},"Kansas":{"inferiors":["Indiana","North Carolina"],"superiors":["Wisconsin","New York","California"]},"Nevada":{"inferiors":["California","New Mexico","Illinois","Texas","Missouri","Virginia","District of Columbia","Ohio","North Carolina","Michigan","Maryland","Colorado","Arizona","Oregon","Indiana","Kentucky","Louisiana","Florida","Hawaii","Massachusetts","South Carolina","Mississippi","Minnesota","North Dakota","New Hampshire","Rhode Island","Washington","Utah","New Jersey","Nebraska","Alabama","South Dakota"],"superiors":["Tennessee","Oklahoma","Wisconsin"]},"Oregon":{"inferiors":["Ohio","Indiana","North Carolina","Michigan","Alabama","South Dakota"],"superiors":["New York","Tennessee","Massachusetts","Oklahoma","Wisconsin","California","Nevada","Alaska"]},"Alabama":{"inferiors":["Ohio","Iowa","North Carolina"],"superiors":["Tennessee","Nevada","Alaska","Nebraska","New Mexico","New Jersey","Kentucky","Oregon","Rhode Island","Illinois"]},"Arizona":{"inferiors":["Indiana","Ohio","North Carolina","Michigan","New Hampshire"],"superiors":["California","New York","Tennessee","Massachusetts","Wisconsin","Nevada","New Mexico","Alaska","Hawaii"]},"Florida":{"inferiors":["Indiana","Ohio","North Carolina","Michigan","Iowa","Idaho","South Dakota"],"superiors":["Tennessee","New York","Massachusetts","Wisconsin","California","New Mexico","Oklahoma","Nevada","Alaska","Hawaii"]},"Georgia":{"inferiors":["Ohio"],"superiors":["Tennessee","New York","Oklahoma"]},"Indiana":{"inferiors":["Ohio","North Carolina","Michigan","South Dakota"],"superiors":["New York","California","Arizona","Illinois","Texas","Pennsylvania","Florida","Oklahoma","Tennessee","Wisconsin","Oregon","District of Columbia","Maryland","Virginia","Washington","Missouri","Nebraska","Colorado","Kansas","Kentucky","Nevada","Louisiana","New Mexico","Minnesota","Rhode Island","Connecticut","Mississippi","Alaska","New Jersey"]},"Montana":{"inferiors":["North Carolina"],"superiors":["Massachusetts","Oklahoma","New Mexico"]},"Arkansas":{"inferiors":["South Dakota","Ohio","Michigan"],"superiors":["New York","California"]},"Colorado":{"inferiors":["Ohio","Michigan","North Carolina"],"superiors":["New York","Tennessee","Massachusetts","Wisconsin","California","Nevada"]},"Illinois":{"inferiors":["Indiana","Ohio","Michigan","South Dakota","Alabama","North Carolina"],"superiors":["New York","California","Tennessee","Massachusetts","Oklahoma","Wisconsin","Nevada","New Mexico","Hawaii"]},"Kentucky":{"inferiors":["Ohio","Indiana","Michigan","North Carolina","Idaho","South Dakota","New Hampshire"],"superiors":["New York","Tennessee","Massachusetts","Wisconsin","Nevada","California","Oklahoma","Hawaii","New Mexico","Alaska"]},"Maryland":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Idaho","South Dakota"],"superiors":["New York","Tennessee","Massachusetts","Oklahoma","California","Wisconsin","Nevada","New Mexico"]},"Michigan":{"inferiors":[],"superiors":["Florida","New York","California","Illinois","Texas","Pennsylvania","Arizona","Tennessee","Oklahoma","Wisconsin","Nevada","New Mexico","District of Columbia","Missouri","Virginia","North Carolina","Ohio","Washington","Georgia","Maryland","Nebraska","Colorado","Indiana","Oregon","Louisiana","Kentucky","Massachusetts","Hawaii","Rhode Island","Mississippi","Utah"]},"Missouri":{"inferiors":["Ohio","North Carolina","Michigan","Indiana"],"superiors":["Tennessee","Oklahoma","Wisconsin","California","Nevada","New Mexico","New York","Massachusetts","Hawaii"]},"Nebraska":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Idaho","South Dakota","Alabama"],"superiors":["New York","Tennessee","California","New Mexico","Oklahoma","Nevada","Alaska"]},"New York":{"inferiors":["California","Illinois","Texas","Pennsylvania","Arizona","Florida","Indiana","Ohio","North Carolina","Michigan","Washington","Colorado","District of Columbia","Maryland","Kentucky","Oregon","Massachusetts","New Mexico","Minnesota","Missouri","Nebraska","Virginia","Kansas","Louisiana","Georgia","Hawaii","Arkansas","Utah","Rhode Island","Mississippi","Idaho","South Dakota","South Carolina","New Jersey","Connecticut","New Hampshire"],"superiors":["Wisconsin","Tennessee","Oklahoma"]},"Oklahoma":{"inferiors":["Nevada","California","New Mexico","Illinois","Texas","Missouri","Virginia","District of Columbia","Ohio","North Carolina","Michigan","Wisconsin","Oregon","Maryland","Washington","Indiana","New York","Hawaii","Minnesota","Kentucky","Pennsylvania","Georgia","Florida","Louisiana","Idaho","South Dakota","Nebraska","Rhode Island","Connecticut","Mississippi","South Carolina","New Jersey","New Hampshire","Montana","Kansas"],"superiors":["Tennessee"]},"Virginia":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Iowa","Idaho","South Dakota"],"superiors":["Tennessee","Oklahoma","Wisconsin","California","Nevada","New Mexico","New York","Alaska","Hawaii"]},"Louisiana":{"inferiors":["Indiana","Ohio","Michigan","Idaho","South Dakota"],"superiors":["Nevada","New York","California","Tennessee","New Mexico","Oklahoma"]},"Minnesota":{"inferiors":["Ohio","North Carolina","Idaho","Alabama","Iowa","South Dakota","Michigan","Indiana","New Hampshire"],"superiors":["Wisconsin","New York","California","Massachusetts","New Mexico","Tennessee","Oklahoma","Hawaii","Alaska","Nevada"]},"Tennessee":{"inferiors":["Illinois","Washington","Florida","Colorado","District of Columbia","Texas","Maryland","Kentucky","Oregon","Arizona","Ohio","Oklahoma","Wisconsin","Nevada","California","New Mexico","Missouri","Virginia","North Carolina","Michigan","Georgia","Nebraska","Indiana","Pennsylvania","New York","Hawaii","Minnesota","Louisiana","Rhode Island","Mississippi","Utah","Alaska","New Jersey","Alabama","South Dakota"],"superiors":[]},"Wisconsin":{"inferiors":["Nevada","California","New Mexico","Illinois","Texas","Missouri","Virginia","District of Columbia","Ohio","North Carolina","Michigan","Oregon","Maryland","Washington","Indiana","Massachusetts","Pennsylvania","Florida","Minnesota","New York","Kansas","Arizona","Kentucky","Colorado"],"superiors":["Oklahoma","Tennessee"]},"California":{"inferiors":["Illinois","Texas","Pennsylvania","Arizona","Florida","Indiana","Ohio","North Carolina","Michigan","Missouri","Virginia","District of Columbia","Oregon","Maryland","Washington","Massachusetts","New Mexico","Minnesota","Nebraska","Colorado","Kansas","Kentucky","Louisiana","New Jersey","Idaho","Alabama","Iowa","Arkansas","Utah","Rhode Island","Mississippi","South Dakota","South Carolina","Connecticut","New Hampshire"],"superiors":["New York","Tennessee","Oklahoma","Wisconsin","Nevada","Alaska"]},"New Jersey":{"inferiors":["Iowa"],"superiors":["Alaska","Oklahoma","California","Hawaii","New York","New Mexico","Tennessee","Nevada"]},"New Mexico":{"inferiors":["Illinois","Texas","Missouri","Virginia","District of Columbia","Ohio","North Carolina","Michigan","Pennsylvania","Florida","Minnesota","Indiana","Kentucky","Louisiana","Arizona","Washington","Nebraska","Maryland","South Carolina","New Jersey","Rhode Island","Connecticut","New Hampshire","Mississippi","North Dakota","Colorado","Montana","Kansas","Oregon","Alabama","South Dakota"],"superiors":["Wisconsin","Tennessee","Oklahoma","New York","California","Nevada","Alaska"]},"Washington":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Iowa"],"superiors":["Tennessee","New York","Massachusetts","California","Oklahoma","Wisconsin","New Mexico","Hawaii","Alaska","Nevada"]},"Connecticut":{"inferiors":["Idaho","Indiana","South Dakota","North Carolina","Ohio","New Hampshire"],"superiors":["New York","Oklahoma","New Mexico","Massachusetts"]},"Mississippi":{"inferiors":["Idaho","South Dakota","Ohio","Michigan","Indiana","North Carolina","New Hampshire"],"superiors":["Alaska","Tennessee","Hawaii","New Mexico","Nevada","Massachusetts"]},"North Dakota":{"inferiors":["Ohio","New Hampshire"],"superiors":["Alaska","Tennessee","Hawaii","New Mexico","Nevada","Massachusetts"]},"Pennsylvania":{"inferiors":["North Carolina","Michigan","Indiana","Ohio","New Hampshire"],"superiors":["New York","California","Wisconsin","New Mexico","Massachusetts","Tennessee","Oklahoma","Hawaii"]},"Rhode Island":{"inferiors":["Idaho","South Dakota","Ohio","Michigan","Indiana","North Carolina","New Hampshire","Alabama"],"superiors":["New York","Oklahoma","New Mexico","California","Alaska","Tennessee","Hawaii","Nevada","Massachusetts"]},"South Dakota":{"inferiors":["Ohio","North Carolina"],"superiors":["New York","California","Illinois","Arkansas","Louisiana","Minnesota","Utah","Rhode Island","Florida","Mississippi","Maryland","Idaho","Oklahoma","Nebraska","District of Columbia","Kentucky","Connecticut","Virginia","Indiana"]},"Massachusetts":{"inferiors":["Illinois","Washington","Florida","Colorado","District of Columbia","Texas","Maryland","Kentucky","Oregon","Arizona","Ohio","Pennsylvania","Minnesota","Indiana","North Carolina","Montana","Connecticut","Rhode Island","Kansas","South Carolina","Mississippi","North Dakota","New Hampshire","Missouri","Utah","Louisiana","Michigan"],"superiors":["Wisconsin","New York","California","Nevada","Tennessee"]},"New Hampshire":{"inferiors":[],"superiors":["Oklahoma","New York","New Mexico","California","Pennsylvania","Maryland","South Carolina","Virginia","New Jersey","Rhode Island","Connecticut","Alaska","Nevada","Hawaii","Massachusetts","Mississippi","Minnesota","Arizona","North Dakota","Kentucky","Ohio"]},"North Carolina":{"inferiors":["Michigan"],"superiors":["New York","California","Texas","Illinois","Pennsylvania","Arizona","Florida","Indiana","Ohio","Wisconsin","Tennessee","Oklahoma","New Mexico","Nevada","Washington","Georgia","District of Columbia","Missouri","Maryland","Nebraska","Massachusetts","Minnesota","Colorado","Oregon","Virginia","Kentucky","Rhode Island","Connecticut","Mississippi","Idaho","Montana","Kansas","Alaska","New Jersey","Alabama","South Dakota"]},"South Carolina":{"inferiors":["New Hampshire"],"superiors":["Oklahoma","New York","New Mexico","California","Alaska","Tennessee","Hawaii","Nevada","Massachusetts"]},"District of Columbia":{"inferiors":["Ohio","North Carolina","Michigan","Indiana","Idaho","South Dakota"],"superiors":["New York","Tennessee","Massachusetts","Wisconsin","Oklahoma","California","Nevada","New Mexico","Alaska","Hawaii"]}}

推荐答案

您有部分订单仅不是总订单(并非所有州都在其上级中列出所有其他州/劣等列表)，因此您的分数计算不起作用.国家的得分取决于他们被提及的频率，而不是它们的相对顺序.您需要实现拓扑排序算法.

You have a partial order only not a total order (not all states list all others in their superiors/inferiors list), so your score calculation doesn't work. States end up with a score depending on how often they were mentioned, not what their relative order is. You'll need to implement a topological sort algorithm.

这篇关于为什么我的排序算法无法正确排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！