Java - 数组冒泡排序

Question

1  |  int[] numbers = { 5, 8, 14, 1, 5678 };
2  |  int tempVar;
3  |  for (int i = 0; i < numbers.length; i++)
4  |   {
5  |       for(int j = 0; j < numbers.length; j++)
6  |       {
7  |                if(numbers[i] > numbers[j + 1])
8  |                {
9  |                        tempVar = numbers [j + 1];
10 |                        numbers [j + 1]= numbers [i];
11 |                        numbers [i] = tempVar;
12 |                 }
13 |        }
14 |  }
15 |  for (int i = 0; i < numbers.length; i++)
16 |  {
17 |           System.out.println(numbers[i].toString());
18 |  }

我是一个自学Java的新手。我在冒泡排序方面遇到了一些问题。

我的问题出现在第5行到第7行。据我理解，外部循环从i=0开始，然后内部循环从j=0开始，并且每次递增1直至j=4，此时外部循环将向前推进，i=1。因此，在外部循环推进到i=1之前，应该发生以下情况。

当i=0时，数字i=5。然后内部循环运行：

当j=0时，数字j=5。

当j=1时，数字j=8。

当j=2时，数字j=14。

当j=3时，数字j=1。

当j=4时，数字j=5678。

然后，如果数字i大于数字j+1，则交换这两个数字。

然后我们比较5和5，然后5和8，然后5和14，然后5和1，最后是5和5678，这与冒泡排序的比较方式不同（它将5与8进行比较，然后将8与14进行比较，然后将14与1进行比较，最后将1与5678进行比较）。

我无法理解第5行到第7行中的代码如何导致以应该在冒泡排序中出现的方式比较两个相邻的数字。有人能指出我哪里想错了吗？

如果有人能更详细地解释第5行到第7行的工作原理，那就太好了。如果能提供逐步分解，那就更好了。谢谢！

- Plaka

---

我建议您查看关于冒泡排序的https://en.wikipedia.org/wiki/Bubble_sort页面，并且为了能够可视化排序算法，请查看http://www.sorting-algorithms.com/。 - inquizitive

Answer 1

请看这个视频（链接在此https://www.youtube.com/watch?v=RpRRUQFbePU），从35.00开始就是冒泡排序。你的理解是正确的，冒泡排序比较1和2号元素，如果1号元素大于2号元素，则交换它们，然后比较2和3号元素，以此类推，直到n-1和n号元素。在第一轮中，最大的元素是n号元素。因此，在第二轮中，您不需要检查最后一个元素，只需检查到n-1号元素即可。

每次通过使用索引'j'，对于所有通过使用索引'i'。

因此，在一次传递中，您不使用索引“i”进行交换。

因此，在您的第5行和第7行中。

5  |       for(int j = 0; j < numbers.length; j++)
6  |       {
7  |                if(numbers[i] > numbers[j + 1])

不要使用索引“i”进行比较，而是采用以下方式

7  |                if(numbers[j-1] > numbers[j])

从1开始使用索引'j'。

正如我在之前所说，在每次使用索引'j'进行迭代时，下一次需要少遍历一个元素，因为每次迭代都会将该次迭代的最大元素放置在最后一个位置。因此，你无需在一次迭代完成后再考虑最后一个元素。因此，第五行可以改为

5  |       for(int j = 1; j < numbers.length-i; j++)

因为每次迭代后，'j' 的范围仅减少一个元素。

因此，整个循环是

for(i=0 to n)
{   
   for(j=1 to n-i)
   {
       if(array[j-1]>array[j])
           swap(array[j-1],array[j]);
   }  
}

- Tattu

---

你的解释非常有帮助。谢谢！ - Plaka

Answer 2

您需要在内层循环和外层循环中按照以下方式进行操作：

for (int i = 0; i < numbers.length-1; i++)
{
  for(int j = i+1; j < numbers.length; j++)
   {
     if(numbers[i] > numbers[j])
     {
      tempVar = numbers [i];
      numbers [i]= numbers [j];
      numbers [j] = tempVar;
     }
   }
}

- Hemant Nigam

Answer 3

好的，冒泡排序有多种实现方法，其中一种是由Kinar建议的。在你的情况下，在第5行只是一个接一个地选择索引：

    5  |       for(int j = 0; j < numbers.length; j++)

它迭代整个数组，在第7行，您正在将数组的第j个元素与第i个元素进行比较，即：

    7  |                if(numbers[i] > numbers[j + 1])

当i=0时，数字i=5，然后内部循环运行并将5与数组中从1到第n个索引的所有元素进行比较。如果第i个元素大于number[j+1]，则它将与该数字交换以使数字按升序排列。请记住，在每次迭代结束时，必须至少有一个元素根据排序顺序放置在正确的位置。因此，在第一次ith迭代结束时，数组将如下所示：

    numbers = { 1, 8, 14, 5, 5678 };

现在考虑i=1，数字i=8，然后再次运行内部循环并将其与从第1个元素到第n个索引的所有元素进行比较。如果第i个元素大于number[j+1]，则它将与该数字交换位置。

另一个重要提示是第5行应为：

    5  |       for(int j = 0; j < numbers.length - 1; j++)

因为在第7行你正在访问numbers[j + 1]，当j的值为4时，程序将尝试在第7行的if语句中访问numbers[5]，这将导致错误。希望这可以帮到你。

- Itban Saeed

---

非常感谢您详细的解释！这对我帮助很大。 - Plaka

Answer 4

基本上，您正确地描述了第5到7行的功能。

then the inner loop runs from j is 0 and increases by 1 each time until j reaches 4

这也是正确的，因为 numbers.length 是 5。

numbers[j + 1]

这不可能是正确的。如果j是4，那么j+1就是5，而numbers[5]将抛出一个索引越界异常（或类似的异常）。

- Burkhard

---

感谢您提醒我关于越界异常的问题。 - Plaka

Answer 5

你需要这样做：

public static void bubbleSort(int[] numArray) {

    int n = numArray.length;
    int temp = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 1; j < (n - i); j++) {

            if (numArray[j - 1] > numArray[j]) {
                temp = numArray[j - 1];
                numArray[j - 1] = numArray[j];
                numArray[j] = temp;
            }

        }
    }
}

- Kinnar Vasa

---

哈哈，你只是从这里复制了答案，甚至没有回答他的问题。用完全不同的代码向他展示如何做这件事根本没有帮助。笑死了。https://dev59.com/8mQo5IYBdhLWcg3wZelg - wuno

无论如何，谢谢你的选择。 - Plaka