在 ArrayList 使用冒泡法

Posted by Sinsy on January 23, 2021 About 4 k words and Need 12 min

前言

前几天接到一个类似版本控制的需求,其中某个元素需要排在最后面。遇到问题有点意思,在实现的过程中出现了元素的重复。

实现过程

由于我需要将某个元素排到最后面,第一想法使用冒泡法,将需要的元素依次与后面的元素做一个交换,完成冒泡排序。

bubble

假设 en 你需要转移的元素,完成与 23 这两元素的交换。

正常来说,我们是这样使用的冒泡法的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    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。使用类似这样的方式就出了点差错。

这个是实现的第一版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
    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
3
4
5
6
7
8
9
10
1
2
en
en
en
en
en
en
2
3

和理想差距很大,正常需要结果应该是 1 2 3 en 。但是看第一版输出结果,复制很多相同元素,感觉是 ArrayLst 添加的时候有问题。所以点进去看看,验证自己的猜测。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    // 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 变大的问题。

1
2
3
4
5
6
7
8
9
10
11
12
    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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
en
en
en
2
3
null
null
null
null
null
null
null
null
null
null

解决

既然知道问题是由 System.arraycopy 以及 size 引起的数组复制、容器变大的问题,那就好解决了。

  • 解决重复元素的出现,同时保证下次交换是正确的
  • 保证容器不在变大

所以,第一种解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
    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 直接进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    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/
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文声明。
如您有任何商业合作或者授权方面的协商,请给我留言:550569627@qq.com