冒泡排序算法

Question

我正在研究bubblesort，学习后想出了这段代码。几乎网络上的每个代码都与我的不同。但是我的没问题。

你们能告诉我我做错了吗？

int[] a= {23,1,5,12,1,2,3};

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

    for (int j=1; j<a.length; j++) {

        if(a[j]<a[j-1]) {

            int temp=a[j];

            a[j]=a[j-1];

            a[j-1]=temp;
        }
    }

    System.out.println(Arrays.toString(a));
}

Answer 1

这在技术上是正确的，但不是最优的。您提到的其他解决方案可能包含一个布尔值，以确保在进一步操作之前列表尚未排序。无论如何，您的版本都会执行 O(n^2) 次迭代，即使输入已经排序。

Answer 2

根据 Corman 的文档：

https://books.google.com/books?id=aefUBQAAQBAJ&lpg=PA40&ots=dMbqQt0QiW&dq=Introduction%20to%20Algorithms%20corman%20bubble%20sort&pg=PA40#v=onepage&q=Introduction%20to%20Algorithms%20corman%20bubble%20sort&f=false

"It works by repeatedly by swapping adjacent elements that are out of order"，你的也是。

如书中所述，它不是最佳解决方案，但它在 O(n^2) 时间内完成。你如何实施完全取决于你，但如果我要给它打分，我会给你满分！

冒泡排序算法

Bubble Sort Algorithm

java

sorting

bubble-sort