1

我有一个关于使用数组的冒泡排序的问题。这是一些示例代码：

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;
        for(int i = 0; i < arr.length; i++)
        {
            for(int j = i; j < arr.length-1; j++)
            {
                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吗？

4

2 回答 2

1

What you have there is called selection sort, not bubble sort.

Bubble sort only swaps adjacent elements, but you're going though the rest of the array and finding the minimum, which is exactly what selection sort does.

Since you use arr[j+1], you can rewrite the inner loop to use arr[j] and shift up the range by one, like this:

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

Now it's a bit more clear that you're looking at each other remaining element to find the minimum.

Yes, you can modify any sort that works on arrays to sort an ArrayList instead by just using ArrayList.get instead of array accesses and ArrayList.set instead of array assignments, i.e.:

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);
        }
    }
}

Note that both selection sort and bubble sort are fairly inefficient (O(n^2)), there are more efficient sorting algorithms such as quick-sort or merge-sort (running in O(n log n)).

于 2013-10-19T11:37:12.583 回答
0

第一个循环保存一个元素，i第二个循环检查 之后的每个元素i，即j并将其与i它保存的元素进行比较。如果它们可以交换，算法会交换它们的位置并继续前进。当外循环完成一次迭代时，之前的所有元素i都已排序，因此j从i.

在纸上做一次，这一切都说得通。

编辑：当您完成算法后，第二个循环条件的原因是您i与j+1. 因此，如果您j继续处理数组的最后一个元素，则下一个元素将不存在并引发异常。您也可以使用此代码进行排序ArrayList。只需使用适当的 setter 和 getter 更改代码交换值。

于 2013-10-19T11:23:52.993 回答