java - Java 中的冒泡排序困惑

Question

我有一个关于使用数组进行冒泡排序的问题。下面是一些示例代码:

public class SortArray 
{
    public static void main(String[] args)
    {
        int[] arr = {4,6,4,2,764,23,23};
        sort(arr);
    }
    static void sort(int[] arr)
    {
        int k;
        <b>for(int i = 0; i < arr.length; i++)
        {
            for(int j = i; j < arr.length-1; j++)
            {</b>
                if(arr[i] < arr[j+1])
                {
                    k = arr[j+1];
                    arr[j+1] = arr[i];
                    arr[i] = k;
                }
            }
            System.out.print(arr[i] + " ");
        }   
    }
}

检查数组有两个循环，我知道第一个循环是遍历数组中的每个元素，但是第二个呢？为什么 j 从 i 开始，为什么它的长度会减去 1？

此外，我可以使用冒泡排序对 ArrayList 进行排序吗？

Answer 1

你所拥有的叫做selection sort , 不是 bubble sort .

冒泡排序只交换相邻元素，但您要遍历数组的其余部分并找到最小值，这正是选择排序所做的。

由于您使用 arr[j+1]，您可以重写内部循环以使用 arr[j] 并将范围向上移动一位，如下所示:

for(int j = i + 1; j < arr.length; j++)
{
    if(arr[i] < arr[j])
    {
        k = arr[j];
        arr[j] = arr[i];
        arr[i] = k;
    }
}

现在更清楚了，您正在查看彼此剩余的元素以找到最小值。

是的，您可以修改任何适用于数组的排序以对 ArrayList 进行排序，只需使用 ArrayList.get 而不是数组访问和 ArrayList.set 而不是数组赋值，即:

for(int i = 0; i < arr.size(); i++)
{
    for(int j = i + 1; j < arr.size(); j++)
    {
        if(arr.get(i) < arr.get(j))
        {
            int k = arr.get(j);
            arr.set(j, arr.get(i));
            arr.set(i, k);
        }
    }
}

请注意，选择排序和冒泡排序都相当低效 (O(n^2))，there are more efficient sorting algorithms例如快速排序或合并排序(在 O(n log n) 中运行)。