"在 ArrayList 使用冒泡法
原创
前言
前几天接到一个类似版本控制的需求，其中某个元素需要排在最后面。遇到问题有点意思，在实现的过程中出现了元素的重复。
实现过程
由于我需要将某个元素排到最后面，第一想法使用冒泡法，将需要的元素依次与后面的元素做一个交换，完成冒泡排序。
假设 en 你需要转移的元素，完成与 2 、3 这两元素的交换。
正常来说，我们是这样使用的冒泡法的。
String[] str = new String[]{"1", "en", "2", "3"};
String temp;
for (int i = 0; i < str.length; i++) {
if ("en".equals(str[i])) {
for (int j = i; j < str.length - 1; j++) {
temp = str[j];
str[j] = str[j + 1];
str[j + 1] = temp;
}
break;
}
}但是现在容器使用的不是数组，而是 list。使用类似这样的方式就出了点差错。
这个是实现的第一版
List<String> list = new ArrayList<>();
list.add("1");
list.add("en");
list.add("2");
list.add("3");
int size = list.size();
String temp1;
String temp2;
for (int i = 0; i < size; i++) {
if ("en".equals(list.get(i))) {
for (int j = i; j < size - 1; j++) {
temp1 = list.get(j);
temp2 = list.get(j + 1);
list.add(j, temp2);
list.add(j + 1, temp1);
}
break;
}
}出乎意料的是，输出结果是
1
2
en
en
en
en
en
en
2
3和理想差距很大，正常需要结果应该是 1 2 3 en 。但是看第一版输出结果，复制很多相同元素，感觉是 ArrayLst 添加的时候有问题。所以点进去看看，验证自己的猜测。
// jdk 11 版本
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 检查是否越界
rangeCheckForAdd(index);
// 记录修改次数
modCount++;
final int s;
Object[] elementData;
// 初始化容器
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
// 数组复制
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
// 容器容量加一
size = s + 1;
}add 源码里有一个 System.arraycopy 以及 全局的 size，前者是数组复制的时候，index 到 index + 1 复制，这也是为什么，当 index = 2 的时候 val = "en" ，复制的时候复制了这个到 index = 3 元素相同。后者进行一次 add 已使用的容器大小就会加一。
根据这两个我们可以模拟出第一次实现的时候出现相同元素、以及 size 变大的问题。
String[] str = new String[16];
str[0] = "1";
str[1] = "en";
str[2] = "2";
str[3] = "3";
System.arraycopy(str, 1, str, 2, 14);
System.arraycopy(str, 2, str, 3, 12);
for (String s : str) {
System.err.println(s);
}输出
1
en
en
en
2
3
null
null
null
null
null
null
null
null
null
null解决
既然知道问题是由 System.arraycopy 以及 size 引起的数组复制、容器变大的问题，那就好解决了。
- 解决重复元素的出现，同时保证下次交换是正确的
- 保证容器不在变大
所以，第一种解决方案。
List<String> list = new ArrayList<>();
list.add("1");
list.add("en");
list.add("2");
list.add("3");
int size = list.size();
String temp1;
String temp2;
for (int i = 0; i < size; i++) {
if ("en".equals(list.get(i))) {
for (int j = i; j < size - 1; j++) {
temp1 = list.get(j);
temp2 = list.get(j + 1);
list.remove(temp1);
list.remove(temp2);
list.add(j, temp2);
list.add(j + 1, temp1);
}
break;
}
}复制多的元素要及时删除，这样可以有效避免 System.arraycopy 复制的时候多出来的元素。
第二种，避免使用到 System.arraycopy 这样的方法，使用 list.set 直接进行交换。
List<String> list = new ArrayList<>();
list.add("1");
list.add("en");
list.add("2");
list.add("3");
int size = list.size();
String temp1;
String temp2;
for (int i = 0; i < size; i++) {
if ("en".equals(list.get(i))) {
for (int j = i; j < size - 1; j++) {
temp1 = list.get(j);
temp2 = list.get(j + 1);
list.set(j, temp2);
list.set(j + 1, temp1);
}
break;
}
}总结一下
感觉看源码还是非常有用，无论是在工作中寻找 BUG 的产生还是解决 BUG 等问题。
另外感觉自己对 JDK 代码还不是很熟悉，应该把常用容器的源码都读一下，在使用的时候，可以避免很多坑。
声明
作者: Sinsy
本文链接：https://blog.sincehub.cn/2021/01/23/at-arraylist-bubble/
版权声明：本文为博主原创文章，遵循 <a href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh">CC 4.0 BY-SA </a> 版
权协议，转载请附上原文声明。
如您有任何商业合作或者授权方面的协商，请给我留言：550569627@qq.com
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
