排序算法之冒泡排序

梦里梦外; 2021-09-18 04:20 302阅读 0赞

冒泡排序顾名思义就是整个排序过程就像气泡一样往上升，单向冒泡排序的基本思想就是：给定 n 个数值，从第一个值开始一次对相邻的进行比较，当前面的值大于后面的值的时候，交换位置，依次比较完之后算一轮，n 个值中的最大值将在最后一位，然后对前面的 n-1 位进行第二轮比较，依次类推。

例如: \{ 1, 6, 3, 5, 7, 9, 8, 4 \}  
第一轮：  
1 < 6 位置不变  
\{ 1, 6, 3, 5, 7, 9, 8, 4 \}  
6 > 3 交换位置  
\{ 1, 3, 6, 5, 7, 9, 8, 4 \}  
6 > 5 交换位置  
\{ 1, 3, 5, 6, 7, 9, 8, 4 \}  
6 < 7 位置不变  
\{ 1, 3, 5, 6, 7, 9, 8, 4 \}  
7 < 9 位置不变  
\{ 1, 3, 5, 6, 7, 9, 8, 4 \}  
9 > 8 交换位置  
\{ 1, 3, 5, 6, 7, 8, 9, 4 \}  
9 > 4 交换位置  
第一轮结束，开始第二轮 比较 n-1 个数  
…

public class BubbleSort {
        public static void bubbleSort(int[] arr) {
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = 0; j < arr.length - i - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                System.out.println("第" + (i + 1) + "轮后: " + Arrays.toString(arr));
            }
        }
        public static void main(String[] args) {
            int[] arr = new int[] { 1, 6, 3, 5, 7, 9, 8, 4 };
            bubbleSort(arr);
        }
    }

第1轮后: \[1, 3, 5, 6, 7, 8, 4, 9\]  
第2轮后: \[1, 3, 5, 6, 7, 4, 8, 9\]  
第3轮后: \[1, 3, 5, 6, 4, 7, 8, 9\]  
第4轮后: \[1, 3, 5, 4, 6, 7, 8, 9\]  
第5轮后: \[1, 3, 4, 5, 6, 7, 8, 9\]  
第6轮后: \[1, 3, 4, 5, 6, 7, 8, 9\]  
第7轮后: \[1, 3, 4, 5, 6, 7, 8, 9\]

从输出结果中，可以看出其在第5轮之后就已经排好序了，不要在进行排序了，这个时候说名字已经不会再出现 arr\[j\] > arr\[j+1\] 的情况，可以这样进行优化：

public class BubbleSort {
    
        public static void bubbleSort(int[] arr) {
            for (int i = 0; i < arr.length - 1; i++) {
                boolean success = true;
                for (int j = 0; j < arr.length - i - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        success = false;
                    }
                }
                if (success)
                    break;
                System.out.println("第" + (i + 1) + "轮后: " + Arrays.toString(arr));
    
            }
        }
        public static void main(String[] args) {
            int[] arr = new int[] { 1, 6, 3, 5, 7, 9, 8, 4 };
            bubbleSort(arr);
        }
    }

第1轮后: \[1, 3, 5, 6, 7, 8, 4, 9\]  
第2轮后: \[1, 3, 5, 6, 7, 4, 8, 9\]  
第3轮后: \[1, 3, 5, 6, 4, 7, 8, 9\]  
第4轮后: \[1, 3, 5, 4, 6, 7, 8, 9\]  
第5轮后: \[1, 3, 4, 5, 6, 7, 8, 9\]

然后分析一下时间复杂度和空间复杂度，时间复杂度是最坏 O(n^2)，最好O(n)，空间复杂度是 O(1)，稳定排序，应为在数值相同时，并没有交换两个数值之间的位置。  
时间复杂度计算：  
两层循环，第1次遍历n次(n个元素)，第二次遍历n-1次，… 依次类推。因此，表达式如下：  
n + (n - 1) + (n - 2) + … + 1 = n \* (n + 1) / 2 = O(n^2)