java - 通过数组使用选择排序对数组列表进行排序

Question

我刚刚学完编程类(class)，被要求做一个排序算法，所以我为数组列表做了一个选择排序算法，但是类(class)结束后我的老师说我应该使用数组进行排序？我尝试排序的列表不断增长，所以我认为我不能使用数组？有谁知道他的意思吗？无论如何，这是排序方法。

    private void sortBids() {

            for (int i = 0; i < bids.size() - 1; i++)
            {
                for (int j = i + 1; j < bids.size(); j++)
                {
                    if (bids.get(i).getAmount() > bids.get(j).getAmount()) {

                        Bid temp = bids.get(j);
                        bids.set(j, bids.get(i));
                        bids.set(i, temp);
                    }
                }
            }


}

Answer 1

我认为这是 Selection Sort 的正确实现。 swap方法采用( O(1) 为数组，因此它不会影响结果)。

我可以看到这不是一个数组；它看起来像一个集合( List )。对于数组，它可能如下所示:

private void sortBids(Bid[] bids) {
    for (int i = 0; i < bids.length - 1; i++)
        for (int j = i + 1; j < bids.length; j++)
            if (bids[i].getAmount() > bids[j].getAmount())
                swap(bids, i, j);
}

private static void swap(Bid[] bids, int i, int j) {
    Bid bid = bids[i];
    bids[i] = bids[j];
    bids[j] = bid;
}

但一般情况下 List这是不正确的，因为它可能非常无效(例如 LinkedList )；但对于ArrayList这是可以接受的，因为它就像一个数组。

如果你有一个集合，你必须写一个 Comparator 。这对于您的情况来说微不足道:

Comparator<Bid> SORT_BY_AMOUNT_ASC = Comparator.comparingInt(Bid::getAmount);

因此您可以对 List<Bid> bids 进行排序:

bids.sort(SORT_BY_AMOUNT_ASC);

最后，您可以使用PriorityQueue 。在这种情况下，您所要做的就是将所有元素添加到此队列中并对其进行迭代:

Queue<Bid> queue = new PriorityQueue<>(SORT_BY_AMOUNT_ASC);
queue.addAll(...);

for(Bid bid : queue)
    // sorted bids