0

我在 Java 中创建了一个非常简单的链表：

public class LinkedList {
    class Node {
        public Node next;
        public int item;

        public Node (int item) {
            this.item = item;
        }
    }

    int listSize = 0;
    Node first = null;
    Node last = null;

    public void add(int n) {
        Node node = new Node(n);
        if (first == null) {
            first = node;
        } else {
            last.next = node;
        }
        last = node;
        listSize++;
    }
}

所以在主类中，我将以随机顺序将元素添加到链表中。但是我怎样才能创建一个计算链表中反转次数的方法呢？

到目前为止，我已经设法用 O(N^2) 的运行时间来实现它：

    public int inversionCount() {
        int count = 0;
        Node current = this.first;
        for (int i = 0; i <= this.listSize - 2; i++) {
            Node next = current.next;
            for (int j = i + 1; j < this.listSize; j++) {
                if (current.item > next.item) {
                    System.out.print("(" + current.item + "," + next.item + ")" + " ");
                    count += 1;
                }
                next = next.next;
            }
            current = current.next;
        }
        return count;
    }

然而，正如我所说，这个算法的运行时间是 O(N^2)。我正在尝试实现 O(NlogN) 的运行时间。如何做到这一点？

4

2 回答 2

0

您正在使用复杂度为O(n^2)的冒泡排序

对于链表，适用于复杂度为O(n log n)的算法是Merge Sort。

请参阅此链接列表的合并排序步骤

于 2017-09-19T11:27:55.690 回答
0

在插入排序中，在普通数组上需要 o(n)，即使您使用二进制搜索来查找需要对元素进行排序的位置，也需要 o(n) 才能为数组腾出新空间。在链表中，插入需要 o(1) 并且通过二分查找，您可以获得 o(nlogn) 的复杂度。从那里您可以通过计算要移动的索引的计算减去前一个索引来计算该数组的反转。每次将所有这些计算加起来以获得数字反转。

于 2021-01-06T16:54:47.263 回答