Реализация сортировки выбора в Java

Question

Я сделал эту функцию сортировки в C ++ для Связанный список

void sort()
{
    node* ctr;
    node* innerctr;
    info temp;
    node* max;
    ctr = start;
    while(ctr!=NULL)
    {
        innerctr=ctr->next;
        max=ctr;
            while(innerctr!=NULL)
            {

                if((innerctr->student.name) > (max->student.name))
                {
                    max=innerctr;

                }


                innerctr=innerctr->next;


            }

            //swapping...


        ctr=ctr->next;
    }
}

Мне нужно сделать нечто подобное в Java, и я хочу использовать готовый класс LinkedList, но я немногозапутался, потому что нет указателей.

Answer 1

Проверка java.util.Collections.sort . Нет необходимости реализовывать сортировку и тому подобное в Java, все это в JDK.

Answer 2

С как можно меньшим количеством модификаций, почти то же самое в Java:

class Student {String name = "Joe Doe";}
class Node {
    Node next;
    Student student;
}
class Info {}
public class NodeSorter {

    Node start; 

    void sort()
    {
        Node ctr;
        Node innerctr;
        Info temp;
        Node max;
        ctr = start;

        while (ctr != null)
        {
            innerctr = ctr.next;
            max=ctr;

            while (innerctr != null)
            {
                if ((innerctr.student.name).compareTo (max.student.name) > 0)
                {
                    max = innerctr;
                }
                innerctr=innerctr.next;
            }
            //swapping...
            ctr = ctr.next;
        }
    }
}

• некоторые фиктивные занятия (Студент, Информация)
• Узел обычно является общим, а не фиксированным для Student.
• имена классов с заглавными буквами.
• методы и атрибуты просто разделены точкой
• сравнение с CompareTo (для не чисел)

А вот улучшенная версия с типом «Студент» в качестве параметра для узла:

class Student implements Comparable <Student> {
    String name = "Joe Doe";
    public int compareTo (Student other) {
        if (other == null) return 1;
        return name.compareTo (other.name);
    }   
}
class Node <T> {
    Node <T> next;
    T value;
}
class Info {}
public class NodeSorter {

    Node <Comparable> start;    

    void sort ()
    {
        Node <Comparable> ctr;
        Node <Comparable> innerctr;
        Info temp;
        Node <Comparable> max;
        ctr = start;

        while (ctr != null)
        {
            innerctr = ctr.next;
            max=ctr;

            while (innerctr != null)
            {
                if ((innerctr.value).compareTo (max.value) > 0)
                {
                    max = innerctr;
                }
                innerctr=innerctr.next;
            }
            //swapping...
            ctr = ctr.next;
        }
    }
}

Проблема с неопределенным «началом» унаследована от вас.

Answer 3

• Я не знаю, что значит> для имени в вашем примере
• В приведенном ниже коде используется выбор минимального индекса, а не максимального индекса, как в вашем случае, поэтому вам следует немного изменить это решение. Но идея все та же

источник с этого сайта

public static void selectionSort2(int[] x) {
    for (int i=0; i<x.length-1; i++) {
        int minIndex = i;      // Index of smallest remaining value.
        for (int j=i+1; j<x.length; j++) {
            if (x[minIndex] > x[j]) {
                minIndex = j;  // Remember index of new minimum
            }
        }
        if (minIndex != i) { 
            //...  Exchange current element with smallest remaining.
            int temp = x[i];
            x[i] = x[minIndex];
            x[minIndex] = temp;
        }
    }
}