气泡排序示例

Question

为什么示例1比示例2更常见？对我来说，阅读示例2更容易，但我从未遇到过它作为示例

示例1

bubleSort(Integer arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n-1; i++)
            for (int j = 0; j < n-i-1; j++)
                if (arr[j] > arr[j+1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
        }
    }

示例2

bubleSort(Integer arr[]) {
        boolean isSorted = true;
        for(int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                isSorted = false;
            }
        }
        if (!isSorted) {
            bubleSort(arr);
        }
}

Answer 1

TL; DR第一个版本是Bubblesort的经典版本，第二个版本是它的优化版本。

嗯，第一个版本是Bubblesort的经典实现。第二版是对它的优化。他们在做同样的事情，但是在某些情况下，第二版的性能要好得多。您的第二个版本就是我们所说的自适应算法。它根据当前状态修改其行为。

例如，考虑要给经典的bubbleort一个已经排序的数组；它将执行所有迭代，但不会更改任何内容。此外，它会花光您的CPU时间。另一方面，第二个版本将在第一遍了解数组已被排序，并且会stop执行。