排序（一）之冒泡排序

r囧r小猫 2022-05-15 08:39 113阅读 0赞

### 冒泡排序原理： ###

第一个元素与第二个元素比较，如果第一个元素大，与第二个交换；

第二个元素与第三个元素比较，如果第二个元素大，与第三个交换；

....

第一次循环，找出最大值

...

第二次循环，找出次最大值

图示如下：

![70][]

代码如下：

@Test
        public void bubbleSort0() {
            int[] arr = {1, 2, 0, 9, 3, 65, 8, 9, 0, 3, 1, 8, 6, 4, 9};
            int len = arr.length;
            for (int i = 0; i < len - 1; i++) {
                for (int j = 0; j < len - 1 - i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
            //[0, 0, 1, 1, 2, 3, 3, 4, 6, 8, 8, 9, 9, 9, 65]
        }

### 优化一 ###

有可能在排序过程中，就已经有序了，但是程序还是要循环完，根本没必要，解决方案是 加一个标志，如果在某次大循环中，没有元素位置移动，就证明已经有序，直接跳出for循环。 例如下面：本来就是有序的

@Test
        public void bubbleSort2() {
            int[] arr = {1, 2, 3, 4, 5, 6, 7, 9, 8};
            int len = arr.length;
            for (int i = 0; i < len - 1; i++) {
                boolean isSorted = true; //每次大循环开始初始化
                for (int j = 0; j < len - 1 - i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                        isSorted = false; //有变动，证明还无序
                    }
                }
                if (isSorted) { //没变动，证明已有序
                    break;
                }
            }
            System.out.println(Arrays.toString(arr));
        }

### 优化二 ###

在排序过程中，每次排序完，有序区的长度就会+1，在真正排序过程中，有序区长度可能会大于排序轮数。

解决方案： 把最后一次排序的位置记录下来，这个位置就是无序区的边界，这个位置以后都是有序区。例如下面数据，第一次排序后4与1 交换后为 3 2 1 4 5 6 7 8 9，后面都是有序的，最后一次是4与1交换，记下4的位置2， 0 1 2位置就是无序的，后面位置就是有序的，不用再比较了

public void bubbleSort3() {
            int[] arr = {4, 3, 2, 1, 5, 6, 7, 8, 9};
            int len = arr.length;
            int unSortedBorder = len - 1;
            int lastExchangeIndex=0;
            for (int i = 0; i < len - 1; i++) {
                boolean isSorted = true;
                for (int j = 0; j < unSortedBorder; j++) {
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                        isSorted = false;
                        lastExchangeIndex=j;
                    }
                }
                unSortedBorder = lastExchangeIndex;
                if (isSorted) {
                    break;
                }
            }
            System.out.println(Arrays.toString(arr));
        }

实时内容请关注微信公众号，公众号与博客同时更新：程序员星星

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIzMjY0NjI_size_16_color_FFFFFF_t_70][]

[70]: /images/20220515/c021f417612a43f685ca618289fa3dea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIzMjY0NjI_size_16_color_FFFFFF_t_70]: /images/20220515/fa0cd722b29e49fe8b8f9e3fc0280bc9.png