检查ArrayList是否已排序。

Question

可能是重复问题：
如何确定Java中的列表是否已排序？

在Java中，我有一个名称数组列表，如何检查它是否已排序？ 我不希望它被排序。 我只想让它返回true（如果已排序）和false（如果未排序）。

到目前为止，我有以下代码：

public boolean isSorted()
{
    boolean check = false;

    if (Collection.sort(bank, Bank.getOwner()).equals(bank))
    {
        check = true;
    }
    else
    {
        check = false;
    }      
    return check;
}

getOwner返回所有者姓名。显然，我做错了。

- orange

Answer 1

显而易见的解决方案：

boolean ascending = true, descending = true;
for (int i = 1; i < arr.length && (ascending || descending); i++) {
    ascending = ascending && arr[i] >= arr[i-1];
    descending = descending && arr[i] <= arr[i-1];
}

- Voo

---

这可能比最明显的解决方案更加复杂。 ;) - Peter Lawrey

@Peter 对于我来说，在循环中添加一点小快捷方式的诱惑力量太强了...我太脆弱了 :( - Voo

Answer 2

当然不是最有效的选择，但可能是最简单的选项：

public boolean isCollectionSorted(List list) {
    List copy = new ArrayList(list);
    Collections.sort(copy);
    return copy.equals(list);
}

这将执行浅复制，对其进行排序，然后比较这些列表。

- Dan Hardiker

Answer 3

你只想检查列表是否已排序。这是o(n)操作。相反，你正在对列表进行n*log(n)的排序，然后比较2个列表o(n)。因此，你的算法的总成本是n*log(n)+o(n)。

相反，只需遍历列表并检查当前元素是否大于或等于前一个元素。如果你的列表应按降序排序，请检查当前元素是否小于或等于前一个元素。

显然，元素的比较可以使用自定义Comparator完成。

- AlexR

Answer 4

使用Google Guava，代码可以如下所示：

public class Bank {
    public static final Ordering<Bank> OWNER_ORDERING = new Ordering<Bank>() {

        @Override
        public int compare(Bank left, Bank right) {
            return left.getOwner().compareTo(right.getOwner());
        }
    };


    private String owner;

    public Bank(String owner) {
        this.owner = owner;
    }

    public String getOwner() {
        return owner;
    }
}

然后使用方法如下：

List<Bank> banks = ImmutableList.of(new Bank("C"), new Bank("B"));
boolean ownerOrdered = Bank.OWNER_ORDERING.isOrdered(banks);

...或直接检索已排序的副本：

List<Bank> sortedCopyBanks = Bank.OWNER_ORDERING.sortedCopy(banks);

- Fabian Barney

Answer 5

你的解决方案在最坏情况下是Ω(n log n)。

最好遍历ArrayList并检查每个元素是否小于/大于下一个元素。

- soulcheck

Answer 6

没有JDK调用可以告诉你一个集合是否已排序，你必须实现自己的逻辑来完成这个任务。可能有第三方库已经实现了这个功能。

- Perception

Answer 7

你可以在你的集合中创建一个标记，在sort()函数排序时将该标记设置为true。如果有任何修改，例如add()、move()等，你可以将标记设置为false。这是你可以找到的优化解决方案，但需要一个标记和一个被修改过的集合。

- SHiRKiT

---

一个有序集合如果移除一个元素，怎么可能会变成未排序的呢？ ;) - Voo