通过跳过内循环中的元素来优化冒泡排序

Question

请帮助我理解这两种优化冒泡排序方法背后的逻辑：

方法一

public static void MyBubbleSort()
{

    for (int i=0; i<list.length; i++)
    {
        boolean is_sorted = true;
        for (int j=0; j<list.length-1; j++)
        {
            if (list[j]>list[j+1])

            {

                    int a = list[j];
                    list[j]=list[j+1];
                    list[j+1]=a;
                    is_sorted = false;
                System.out.println ("Ascending order:"+Arrays.toString(list))}

方法二

在这里，我不明白 -i 在内部循环中做了什么。

 public static void MyBubbleSort()
{

    for (int i=0; i<list.length; i++)
    {

        for (int j=0; j<list.length-1-i; j++) // <-- here
        {
            if (list[j]>list[j+1])

            {

                    int a = list[j];
                    list[j]=list[j+1];
                    list[j+1]=a;

                System.out.println ("Ascending order:"+Arrays.toString(list));

Answer 1

在冒泡排序中，在每次迭代结束时，最大的剩余元素到达其最终位置。例如，在下面的数组中。

6 2 5 3 8 7 1

第一次迭代后，8将是数组中的最后一个元素，也就是它的最终位置。

在第二次迭代结束时，7 将是数组中的倒数第二个元素，这是它的最终位置。

因此，在每次迭代之后，我们不需要比较已到达其最终位置的元素。

所以，在第一次迭代之后，我们只需要比较length - 1（这里i = 1）个元素。在第二次迭代结束时，我们只需要比较 length - 2 (i = 2) 个元素。

请在https://en.wikipedia.org/wiki/Bubble_sort link 观看动画。这将有助于更加清晰。

Answer 2

Bubble sort 通过比较向上移动数组的相邻元素来工作。在一个简单的例子中，[3, 2, 1]，内部 (j-index) 循环中的第一个比较在 3 和 2 之间； 3“获胜”并与2交换。然后比较3和1，3再次“获胜”并位于数组的最后一个索引中，然后是[2, 1, 3]第一次通过后。

实际上，内部 (j-index) 循环的目的是将最大的元素移动到数组的后面。最大的元素将“赢得”一路上的所有比较。

因此，经过一个运行外层循环后，最后一个元素肯定是排序好的，是最大元素，在它的最后位置，永远不需要重新检查。在外部循环的两个运行之后，最后两个元素位于它们的最终位置并且永远不需要重新检查。按照这个逻辑，我们可以在 end - i - 1 处停止内部循环以保存无意义的比较。

如果您不信服，请在每个内部循环后打印整个数组运行使用玩具示例：

import static java.lang.System.out;

class Main {
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j+1]) {
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
                }
            }

            print(arr, i);
        }
    }

    public static void print(int[] arr, int p) {
        int i = 0;
        out.print(
            "after " + (p + 1) + (p + 1 == 1 ? 
            " pass:   " : " passes: ") + "[ "
        );

        while (i < arr.length - 1 - p) {
            out.print(arr[i++] + ", ");
        }

        out.print("(");

        while (i < arr.length - 1) {
            out.print(arr[i++] + ", ");
        }

        out.println(arr[i] + ") ]");
    }

    public static void main(String[] args) {
        int[] arr = {9,5,7,1,4,7,2};
        bubbleSort(arr);
    }
}

输出

after 1 pass:   [ 5, 7, 1, 4, 7, 2, (9) ]
after 2 passes: [ 5, 1, 4, 7, 2, (7, 9) ]
after 3 passes: [ 1, 4, 5, 2, (7, 7, 9) ]
after 4 passes: [ 1, 4, 2, (5, 7, 7, 9) ]
after 5 passes: [ 1, 2, (4, 5, 7, 7, 9) ]
after 6 passes: [ 1, (2, 4, 5, 7, 7, 9) ]
after 7 passes: [ (1, 2, 4, 5, 7, 7, 9) ]

位于最终位置且永远不需要触摸的元素用括号分隔。你可以看到他们一直保持原状。如果您好奇的话，可以尝试一下代码。尝试反向排序并使用各种输入。

顺便说一句，还有一些额外的优化。例如，请注意在上面的示例中，经过 5 次遍历后，数组已完全排序。添加一个布尔标志以确定是否在给定的传递中执行了交换允许您提前退出并跳过一些最终迭代。

不过，这些改进中的

None 有助于降低 O(n²) 时间复杂度。在最坏情况下，排序花费的时间与输入大小成正比增长。

通过跳过内循环中的元素来优化冒泡排序

Optimizing Bubble Sort by skipping elements in the inner loop

java

sorting

bubble-sort

方法一

方法二

输出