Bubble Sort（冒泡排序）

介绍

排序原理：

1. 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。

2. 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。

数组的简单实现

package sorting;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] testArray1 = {1, 7, 11, 0,23,12, 2120, 2, 3, 6, 5, 6};
        int[] testArray2 = {1, 7, 11, 0,23,12, 2120, 2, 3, 6, 5, 6};

        bubbleSort(testArray1);
        System.out.println(Arrays.toString(testArray1));

        Arrays.sort(testArray2);
        System.out.println(Arrays.toString(testArray2));
        Arrays.stream(testArray1).min();
    }

    public static void swap(int[] nums, int a, int b) {
        int temp;
        temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public static void bubbleSort(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums,j, j + 1);
                }
            }
        }
    }
}

利用comparable接口的实现

package cn.itcast.algorithm.sort;

public class Bubble {
    /*
       对数组a中的元素进行排序
    */
    public static void sort(Comparable[] a){
        for(int i=a.length-1;i>0;i--){
            for(int j=0;j<i;j++){
                //{6,5,4,3,2,1}
                //比较索引j和索引j+1处的值
                if (greater(a[j],a[j+1])){
                    exch(a,j,j+1);
                }
            }
        }
    }

    /*
        比较v元素是否大于w元素
     */
    private static  boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }

    /*
    数组元素i和j交换位置
     */
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}

算法的performance

T(n) = O($n^2$)