помощь в написании быстрой сортировки

Question

Я пишу Java-приложение.У меня есть класс с именем Node.Я создал объект ArrayList и добавил в него несколько узлов.каждый узел имеет целочисленные данные и двойную вероятность.Я хочу отсортировать узел в arrayList по их вероятности.Я написал следующий метод:

     private void sort(ArrayList<Node> list2) {
    int n = list2.size();
    for (int i = 1; i < n; i++) {
        int m = list2.get(i);
        int j = i - 1;
        while ((j >= 0) && (list2.get(j).prob > m.prob))
            list2.set(j + 1, list2.get(j--));
        list2.set(j + 1, m);
      }

     }

Но это не быстрый способ сортировки.Как я могу сортировать быстрее?Могу ли я использовать метод Collections.sort () в Java для этой цели?Как ?не могли бы вы вести меня?

Answer 1

Да, вы можете использовать Collections.sort() - и это почти наверняка правильно.Вы должны по крайней мере сделать это, чтобы начать, и сравните это, чтобы увидеть, достаточно ли это быстро.Возможно, вам удастся добиться большего, если у вас будет больше информации о списке (например, он, скорее всего, будет «в основном отсортирован» для начала), но простой подход - хорошая отправная точка.

Обратите внимание, что ваш образецкод не соответствует вашему описанию - вы описали ArrayList<Node>, но ваш код только для ArrayList<Integer>.

Answer 2

Да, вы можете (и должны) использовать Collections.sort ().Этот способ сортировки уже оптимизирован и, вероятно, всегда будет работать быстрее, чем реализация, которую вы, вероятно, напишите сами.

Однако ваш код в настоящее время не применяется к Collections.sort ().Для этого объекты, которые вы помещаете в свой список, должны иметь поля «данные» и «вероятность».

Вот краткий пример:

public class DataProbability implements Comparable<DataProbability> {
    private int data;
    private double probability;

    public int getData() {
        return data;
    }

    public double getProbability() {
        return probability;
    }

    public int compareTo(DataProbability pProb) {
        return Double.compare(getProbability(), pProb.getProbability());
    }
}

// Later, with your list
List<DataProbability> lDataList = new ArrayList<DataProbability>();
// Add some elements
Collections.sort(lDataList);

При сортировке списка выесть 2 варианта:

• Убедитесь, что сортируемые объекты реализуют интерфейс Comparable (это то, что я только что использовал
• Или вы также можете указать Comparator для использования при вызовеCollections.sort ()

Answer 3

Сопоставимый интерфейс должен быть реализован при сортировке определенных пользователем объектов.Для этого вам также потребуется переопределить методы equals () и hashcode ().Однако это не требуется для сортировки списка, который содержит только объекты примитивного типа данных.