java - 选择排序时间

Question

我编写了一个快速选择排序程序，如下所示:

public static ArrayList<Integer> selectionSort(ArrayList<Integer> list) {
        for (int i=0; i < list.size()-1; i++) {
            int smallestElement = i;
            for (int j=i+1; j < list.size(); j++) {
                if (list.get(j) < list.get(smallestElement)) {
                    smallestElement = j;
                }
            }
            swapPosition(list, smallestElement, i);
        }

        return list;
    }

    public static void swapPosition(ArrayList<Integer> list, int first, int second) {
        Collections.swap(list, first, second);
    }

在我的主程序中，我计算程序运行所需的时间(以毫秒为单位)。我创建了一个包含 1000 个项目的新 ArrayList，这些项目已经排序并计算了最佳情况场景时间。然后，我颠倒了 1000 个项目的顺序，以表示必须交换所有项目的最坏情况，但由于某种原因，我最坏情况所需的时间比最好情况要少。在最好的情况下，不需要交换任何东西。 为什么我的程序在最好的情况下比在最坏的情况下运行需要更多的时间？以下是其余部分的代码:

ArrayList<Integer> bestCase = new ArrayList<Integer>();
        for (int i=1; i < 1001; i++) {
            bestCase.add(i);
        }
        long startTimeBest = System.currentTimeMillis();
        selectionSort(bestCase);
        long endTimeBest = System.currentTimeMillis();
        long totalTimeBest = endTimeBest - startTimeBest;
        System.out.println("Total time of this program in the best case "
                + "scenario is: " + totalTimeBest + " millisecond(s)");

        Collections.reverse(bestCase);
        long startTimeWorst = System.currentTimeMillis();
        selectionSort(bestCase);
        long endTimeWorst = System.currentTimeMillis();
        long totalTimeWorst = endTimeWorst - startTimeWorst;
        System.out.println("Total time of this program in the worst case "
                + "scenario is: " + totalTimeWorst + " millisecond(s)");

最好情况下的时间为 16 毫秒，最坏情况下为 4 毫秒。这没有道理。

Answer 1

除了测试技术问题之外，似乎还有另一个问题。

"I then reversed the order of the 1000 items to signify the worst case scenario when all the items must be swapped, but my worst case scenario takes less time than my best case for some reason. In the best case, nothing should have to be swapped."

在您的程序中，执行的交换次数(swapPosition(...) 调用)并不取决于要排序的元素的顺序。

执行的smallestElement = j;指令的数量取决于顺序。