数据结构和算法（二）算法排序——冒泡

所谓“冒泡”，就是通过迭代比较元素大小，将大值元素通过内层迭代像冒泡一样逐渐交换到最后！

外层迭代确定通过几轮“大筛选”

内层迭代确定将大致逐渐向后挪

基本实现：

package com.jun.sort;

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        Integer[] arr = {5,8,6,3,9,2,1,7};
        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 swap = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = swap;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

 

结果：
[1, 2, 3, 5, 6, 7, 8, 9]

Java模块化方法实现：

package com.jun.sort;

import java.util.Arrays;

public class BubbleSort{

    private static Integer[] arr = {5,8,6,3,9,2,1,7};

    /*比较大小*/
    private static boolean getVlue(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }

    /*交换*/
    private static void swap(Comparable[] arr, int i, int j) {
        Comparable swap = arr[j];
        arr[j] = arr[i];
        arr[i] = swap;
    }

    private static void sort(Comparable[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - i - 1; j++) {
                if (getVlue(a[j], a[j + 1])) {
                    swap(a, j, j + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

改进： 

        Integer[] arr = {5,8,6,3,9,2,1,7};
        for (int i = 0; i < arr.length - 1; i++) {
            boolean b = false ; //用于判断在本轮循环中是否发生交换，如果没有，则后几轮就无须执行了！
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int swap = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = swap;
                    b = true;
                }
            }
            if (!b) {
                break;
            }
        }
        System.out.println(Arrays.toString(arr));

时间复杂度O(n^2)