数据结构 冒泡排序

　　基本思想：假设待排序表长为n，从后往前（或从前往后）两两比较相邻元素，如果是逆序（A[i-1] > A[i]），那么交换这两个元素，直到序列比较完。这是一趟冒泡，将最小的元素交换到待排序列的第一个位置（最小元素如同气泡一样逐渐往上“漂浮”直至“水面”，这是冒泡排序名字的由来）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少了一个元素，每趟冒泡把待排序列中的最小元素放到了最终位置上，最多做n-1趟冒泡就能完成排序任务。冒泡排序产生的有序子序列是全局有序的，因为有序子序列中的所有元素小于或大于无序子序列中的所有元素，每一趟排序都会将一个元素放到最终位置上。

　　

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int maxIndex = arr.length - 1;
        for (int i = 0; i < maxIndex; i++) {
            // 本趟冒泡是否发生交换的标志
            boolean isSwap = false;
            // 一趟冒泡过程
            for (int j = maxIndex; j > i; j--) {
                // 如果相邻元素出现逆序
                if (arr[j - 1] > arr[j]) {
                    // 交换相邻元素
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    
                    isSwap = true;
                }
            }
            
            // 如果本趟冒泡没有发生交换，说明表已经有序
            if (!isSwap) {
                return;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {1, -1, 3, 2, -3};
        BubbleSort.bubbleSort(arr);
        for (int item : arr) {
            System.out.print(" " + item);
        }
    }
}

　　输出结果：

 -3 -1 1 2 3

　　冒泡排序性能分析：

　　空间复杂度：仅使用了常数个辅助单元，空间复杂度为O(1)。

　　时间复杂度：当初始序列有序时，第一趟冒泡后发现没有交换元素，跳出循环，比较次数为n-1，移动次数为0，即最好情况下的时间复杂度为O(n)。当初始序列逆序时，需要n-1趟排序，第i趟排序要进行n-i次元素比较，而且每次比较后移动元素3次来交换元素。在这种情况下，

　　

　　所以，最好情况下时间复杂度为O(n)，最坏情况下时间复杂度为O(n²)，平均情况下时间复杂度为O(n²)。

　　稳定性：因为当i>j且A[i]=A[j]时，不会交换元素，所以冒泡排序是稳定的。

 

　　参考资料

　　《2017年数据结构联考复习指导》 P287

　　图解排序算法(一)之3种简单排序(选择，冒泡，直接插入)