冒泡排序 Bubble Sort

1. 前言

它是一种比较简单的排序算法，会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次比较相邻两个数的大小，如果前者比后者大，则交换位置。这样一次遍历之后，最大的元素就在数列的末尾。
重复此操作，直到数列都有序为止。

2. 实现

下面以数列[20,40,30,10, 60, 50]为例，演示它的冒泡排序过程：

3. 复杂度与稳定性

• 复杂度：O(n2)，假设被排序的数列有N个树，遍历一趟的时间复杂度为O(n)，需要遍历n-1次

• 稳定性：冒泡排序是稳定的算法，它满足稳定算法的定义（假设在数列中存在a[i] = a[j]，若排序之前a[i]在a[j]之前，并且排序之后a[i]仍在a[j]前面，则这个算法是稳定的）

4. 代码实现

/**
 * @author xiaoyuge
 */
public class BubbleSort {
    public static void bubbleSort(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    //交换
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {20,40,30,10,60,50};
        bubbleSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.printf("%d ", a[i]);
        }
    }
}