java-сортировать связанный список строк на основе их целочисленных значений

Question

У меня есть связанный список строк, каждая из которых имеет целочисленное значение из расчета. Чтобы объяснить вещи проще, у меня есть связанный список строк, представляющих узлы. У каждого узла есть расстояние. Чтобы получить расстояние, вы используете метод, который я создал в моей программе, чтобы вернуть расстояние этого узла. Я хочу, чтобы этот связанный список сортировался по каждому расстоянию строки, от самого низкого до самого высокого. Как бы я это сделал? Вот пседокод

Queue<String> someStringList = new LinkedList<String>();

...

for each of the nodes in the list

String node = ((LinkedList<String>) someStringList).get(i);
distance = theNodesDistance(node);
sort the linked list by the node's distance
...

public int theNodesDistance(String str){
return distance;

}

Answer 1

А как насчет класса Node?

class Node{
   String str;
   int distance;
   public Node(String str){
       this.str = str;
       this.distance = theNodesDistance(str);
   }
}

Тогда вы можете переопределить Comparator. Я предлагаю вам использовать PriorityQueue вместо LinkedList, чтобы ваши вставки в упорядоченный список могли быть более эффективными (O (logn)). В этом случае вам на самом деле не нужно вызывать функцию сортировки или heapify, поскольку очередь приоритетов всегда поддерживает порядок узлов.

PriorityQueue que = new PriorityQueue(new Comparator<Node>(){
     public int compare(Node n1, Node n2){
          if(n1.distance < n2. distance) return -1;
          else if(n1.distance > n2.distance) return 1;
          return 0;
     }
});

Вы можете добавить в очередь следующим образом:

for(each str){
    que.add(new Node(str));
}

Answer 2

Вы можете использовать сортировку алгоритма. как выборы выбора, сортировка пузырей ... Это тип вставки

double temp;
for(int i = 1;i<yourList.size();i++)
{
temp = thenodedistance(yourlist.get(i));
int j = i;
    while(j>0&&thenodedistance(yourlist.get(j-1))> temp)
    {
        yourlist.add(j,yourlist.remove(j-1);
        j--;
    }
    yourlist.add(j,yourliste.remove(i));
}

таким образом вы можете отсортировать свой список (не пробовал код ....)

Answer 3

Если вы можете позволить себе тратить ЦП на повторные вычисления расстояния, то вы можете использовать методы сортировки JDK с реализацией Comparator, которая рассчитывает расстояние от любых 2 строк и сравнивает их. Это самое простое.

Если вы предпочитаете вычислять только один раз расстояние для каждой строки (предполагая, что это дорого), то вы либо:

a) создать новую коллекцию кортежей (строка и расстояние) и отсортировать кортежи по расстоянию (снова с помощью компаратора или путем сопоставления класса кортежей).

b) или вы можете попытаться кэшировать расстояния в хэш-карте строк-расстояний, на которые будет полагаться компаратор.

Answer 4

Вы можете использовать TreeMap. Ниже приведена нормальная демонстрация -

    TreeMap<Integer, String> tmap = new TreeMap<Integer, String>(); 
/*Adding elements to TreeMap*/
 tmap.put(1, "Data1"); 
tmap.put(23, "Data2"); 
tmap.put(70, "Data3"); 
tmap.put(4, "Data4"); 
tmap.put(2, "Data5"); 
/* Display content using Iterator*/ 
Set set = tmap.entrySet();
 Iterator iterator = set.iterator();
 while(iterator.hasNext()) { 
Map.Entry mentry = (Map.Entry)iterator.next();
 System.out.print("key is: "+ mentry.getKey() + " & Value is: ");
 System.out.println(mentry.getValue()); 
} 

Вывод ::

key is: 1 & Value is: Data1 
key is: 2 & Value is: Data5 
key is: 4 & Value is: Data4 
key is: 23 & Value is: Data2 
key is: 70 & Value is: Data3

Answer 5

Первый вариант - создать компаратор, а затем отсортировать коллекцию.Я бы сделал что-то вроде:

  public static void main(String... arg) {
        LinkedList<String> someStringList = new LinkedList<>();

        someStringList.add("2");
        someStringList.add("1");

        System.out.println(someStringList);

        Collections.sort(someStringList, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return theNodesDistance(s1).compareTo(theNodesDistance(s2));
            }

        });
        System.out.println(someStringList);

    }
    public static Integer theNodesDistance(String str){
        return Integer.parseInt(str); // here return the distance
    }

Другой вариант - создать класс Node с идентификатором и расстоянием:

public class Node implements Comparable<Node> {

    String id;
    Integer distance;

    public Node(String id) {
        this.id = id;
        this.distance = theNodesDistance(id);
    }

    @Override
    public int compareTo(Node node) {
        return this.distance.compareTo(node.distance);
    }

    public String toString() {
        return id;
    }

    public Integer theNodesDistance(String str){
        return Integer.parseInt(str);
    }
}

Затем отсортировать список, выполнив:

LinkedList<Node> nodes = new LinkedList<>();

nodes.add(new Node("2"));
nodes.add(new Node("1"));

System.out.println(nodes);

Collections.sort(nodes);
System.out.println(nodes);

Наконец, вы можете использовать PriorityQueue, который организует элементы всякий раз, когда вы вставляете новый узел.Я имею в виду, вы можете удалить каждый узел по порядку.

Queue<Node> nodes = new PriorityQueue<>();
nodes.add(new Node("10"));
nodes.add(new Node("3"));
nodes.add(new Node("2"));
nodes.add(new Node("1"));
nodes.add(new Node("4"));

System.out.println(nodes.remove());
System.out.println(nodes.remove());
System.out.println(nodes.remove());
System.out.println(nodes.remove());
System.out.println(nodes.remove());

В этом случае вывод будет:

1
2
3
4
10