java - 数组越界 [ArrayList 的冒泡选择]

Question

我正在编写一个气泡选择方法，该方法应该与这些凭据一起使用:

/* Write code for a Bubble Sort algorithm that starts at the right side of
 * of ArrayList of Comparable objects and "bubbles" the largest item to the
 * left of the list.  The result should be an ArrayList arranged in descending
 * order.
 */
 @SuppressWarnings("unchecked") 
 void bubbleSort(ArrayList <Comparable> list) {

    int end = list.size();

    for (int i = 0 ; i < end; i++){
        for (int j = end; j > 0; j--){
            if ( list.get(j).compareTo(list.get(j-1)) > 0 ){
                //swap
                Comparable temp = list.get(j);
                list.set(j,list.get(j - 1));
                list.set(j - 1, temp);
                //System.out.println(list);
            }
        }   
        end--;
    }
}

问题是，Java 会告诉我它超出了范围。

如果我改用

for (int j = end - 1; j > 0; j--)

然后代码将运行，但是它不会运行列表完全完成排序所需的运行次数(也就是它会提前停止一个循环)

Answer 1

正如所解释的，您需要从 end-1 开始，否则您将访问数组越界。

<小时/>

假设您有一个整数数组:5 1 4

你的算法会这样做:

第一次迭代 -> i = 0/j 从 2 开始

1 5 4

第二次迭代 -> i = 1/j 从 1 开始

现在它只会比较 5 和 1 而不会切换它们，因为 5 更高。那么，4 和 5 呢？他们应该交换。您的算法实现是错误的。

如果删除 end--; 它应该可以工作。不过，这可以优化