2

我有两种冒泡排序的实现，但其中一种工作正常，另一种没有任何人可以解释这两者有什么区别

第一个这个工作正常

private static int[] sortBuble(int[] a) {
        boolean swapped = true;
        for (int i = 0; i < a.length && swapped; i++) {
            swapped = false;
            System.out.println("number of iteration" + i);

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

                if (a[j - 1] > a[j]) {
                    int temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;
                    swapped = true;
                }
            }
        }

        return a;
    }

第二个这不起作用，但它们看起来或多或少相同

private static int[] sortBuble1(int[] a) {
        boolean swapped = true;
        for (int i = 0; i < a.length && swapped; i++) {
            swapped = false;
            System.out.println("number of iteration" + i);

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

                if (a[i] > a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    swapped = true;
                }
            }
        }

        return a;
    }
4

2 回答 2

3

他们不一样。在第二个示例中，您为内部 for 循环的每次迭代都保持 i 不变，并使用a[i]for 比较，这是不正确的。正如我在另一个答案中所说，第一个也是低效的。以下是第一个的优化版本：

private static int[] bubblesort(int[] nums)
{
    boolean done = false;

    for (int i = 0;  i < nums.length && !done; i++)
    {
        done = true;

        for (int j = nums.length-1; j > i; j--)
        {
            if (nums[j] < nums[j-1])
            {
                int temp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = temp;
                done = false;
            }
        }
    }

    return nums;
}

在第 i次迭代结束时，我们知道前 i 个元素已排序，因此我们不再需要查看它们。我们需要布尔值来确定是否需要继续。如果没有进行交换，那么我们就完成了。我们可以删除布尔值，它仍然可以工作，但效率会降低。

于 2013-11-10T07:05:02.140 回答
1

不同之处在于用于数组的索引。

在第一种情况下，您的内部for循环 withj独立于i. 此外，您j在交换时使用相邻的值，以便您始终交换数组中的相邻值。

在第二种情况下，您的内部for循环j从i + 1. 你同时使用i和j来索引你的数组。所以你实际上不是在比较相邻的元素，而是比较可能相距很远的元素（例如，wheni=1和j=4）。那不是冒泡排序，这个算法不会那样工作。

于 2013-11-10T07:06:33.043 回答