Java 随机 ListArray 上的冒泡排序

Question

我正在练习 Java，并且可以对 int[] 数组进行冒泡排序。我想知道是否可以为自己制作一个更困难的示例，因此我制作了一个随机长度的 ArrayList，每个元素中包含随机数。

问题是，当进行冒泡排序时，有时在调用 bubbleSort2 后不会打印任何内容。由于某种原因，我无法在 bubbleSort2 方法中使用 foreach 循环。

另外请告诉我我对 List 和 ArrayList 的使用是否正确。

import java.util.ArrayList;
import java.util.List;

public class BubbleSort
{

    public static void main(String[] args)
    {
        List<Integer> myList2 = new ArrayList<Integer>();
        int min = 2;
        int max = 30;
        for (int i=0; i<(int)(Math.random() * ( max - min) + min); i++)
        {
            myList2.add((int)(Math.random() * 100));
        }

        System.out.println("Unsorted list 2");
        for (int element: myList2)
        {
            System.out.print(element + " ");
        }
        System.out.println("");

        System.out.println("Bubble sorted list 2 (BubbleSort2)");
        bubbleSort2(myList2);
        for(int element: myList2)
        {
            System.out.print(element + " ");
        }
    }

    public static void swap2(List<Integer> x, int i, int j)
    {
        Integer temp = x.get(i);
        x.set(i, x.get(j));
        x.set(j, temp);
    }

    public static void bubbleSort2(List<Integer> x)
    {
        int mostRightSwap = x.size() - 1;
        while (mostRightSwap > 0)
        {
            for (int i=0; i<x.size()-1; i++)
            {
                if (x.get(i) > x.get(i + 1))
                {
                    swap2(x, i, i + 1);
                    mostRightSwap = i;
                }
            }
        }
    }

}

更新:

我已经找到我的问题了。正如此处和其他地方的 friend 所指出的，当 if 条件从未满足时，我有时会陷入无限循环。所以一行代码 mostRightSwap = 0;添加是为了在 if 语句之前伪造 while 条件，以防 if 语句不执行。

public static void bubbleSort(List<Integer> x)
    {
        int mostRightSwap = x.size() - 1;
        while (mostRightSwap > 0)
        {
            int right = mostRightSwap;
            mostRightSwap = 0;
            for (int i=0; i<right; i++)
            {
                if (x.get(i) > x.get(i+1))
                {
                    swap2(x, i, i+1);
                    mostRightSwap = i;
                }
            }
        }
    }

Answer 1

您的问题基本上是您遇到了无限循环。您的停止条件是，如果最右边的交换元素不是第一个元素，请尝试对数组进行冒泡排序。但现在想象一个这样的场景，具有以下元素。

[1,5,31,17,20]。你认为会发生什么？第一个元素永远不会被交换，并且您会陷入无限循环，因为外部 while 循环条件永远不会使循环停止，因为第一个元素是最低的元素。我宁愿建议一个简单的 boolean 值来检查是否某些内容已被交换为外部 while 循环。

public static void bubbleSort2(List<Integer> x)
{
    boolean swapped = false;
    do
    {
        swapped = false;
        for (int i=0; i<x.size()-1; i++)
        {
            if (x.get(i) > x.get(i + 1))
            {
                swap2(x, i, i + 1);
                swapped = true;
            }
        }
    } while(swapped);
}