超出数组的边界 [使用 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--;它应该可以工作。但是，这可以优化

Answer 2

使用此代码，它将满足数组实现中的要求，其中大小是数组长度。

for (int i = 0; i < size - 1; j++) {
    for (int j = i + 1; j < size - 1; k++){
        if (array[i] > array[j]) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp; 
        }   
    }
}

Answer 3

如果数组长 3，则数组 [3] 超出界。由于您从 array[length] 开始，因此您必须在进入 for 循环之前递减它，就像您提供的代码一样。

Answer 4

使用 end - 1 将比较列表中的最后一个和第二个倒数第二个值如果您使用 end它将尝试比较最后一个值和最后一个之后索引处的值，这将给出ArrayOutOfBound Exception .

现在为了正确输出，您必须删除end--;行

，如下所示

for (int i = 0 ; i < end; i++){
        for (int j = end -1; 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);
            }
        } 
        //remove below line
        end--;
    }

这也会将列表缩短右侧的一个值。所以删除这将起作用