数据结构--冒泡排序

冒泡排序

代码示例

    public  static <E extends Comparable<E>> void sort(E[] data){
        //最后一个不需要遍历到
        for (int i = 0; i < data.length - 1; i++) {
            //arr[n-i, n) 已经排好
            //通过冒泡早arr[n-i-1] 位置放上合适的元素
            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j].compareTo(data[j + 1]) > 0 )
                    swap(data,j, j +1);
            }
        }
    }

    //优化1 如果数组是有序数组
    public  static <E extends Comparable<E>> void sort2(E[] data){
        //最后一个不需要遍历到
        for (int i = 0; i < data.length - 1; i++) {
            //arr[n-i, n) 已经排好
            //通过冒泡早arr[n-i-1] 位置放上合适的元素
            boolean isSwaped = false; //有序数组 不进行交换
            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j].compareTo(data[j + 1]) > 0 ){
                    swap(data,j, j +1);
                    isSwaped = true;
                }
            }
            if (!isSwaped) break;
        }
    }

    //优化2 减少循环轮数 记录在当前轮中最后一次执行swap时j的值  表示data.length - lastSwappedIndex 已经排好序了
    public  static <E extends Comparable<E>> void sort3(E[] data){

        //最后一个不需要遍历到
        for (int i = 0; i < data.length - 1;) {

            //arr[n-i, n) 已经排好
            //通过冒泡早arr[n-i-1] 位置放上合适的元素

           int lastSwappedIndex = 0;

            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j].compareTo(data[j + 1]) > 0 ){
                    swap(data,j, j +1);
                    lastSwappedIndex = j + 1;
                }
            }
            //表示 有几个元素已经排好序了 不用重新循环
            i = data.length - lastSwappedIndex;
        }
    }

    private static <E>  void swap(E[] arr, int i, int j){
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

时间复杂度：O(n^2)

稳定性

排序前相等的俩个元素，排序后相对位置不变。
冒泡排序法是稳定的，每次只比较相邻元素，相同大小的元素没有机会跳跃。