排序：冒泡排序

冒泡排序： 冒泡排序是一直用最简单的排序算法，基本思想是依次比较每一对相邻元素的大小，如果第一个元素大于第二个元素，那么就交换两个元素的位置，直到不需要交换为止。冒泡排序的时间复杂度最差为 O(n²) ，最优为 O(n) 。稳定性：稳定。

举个栗子

基础版

public static void main(String[] args){
    int[] bubbles = {5,3,2,4,6};
    for(int i = bubbles.length - 1; i > 0; i--){
        for(int j = 0; j < i; j++){
	    if(bubbles[j] > bubbles[j+1]){
		int temp = bubbles[j];
		bubbles[j] = bubbles[j+1];
		bubbles[j+1] = temp;
            }
        }
    }
}

上述算法的时间复杂度为 O(n²) ，即使在最好的情况下。

改进版,增加一个标记，在排序过程中如果没有交换，则意味着排序结束。

public static void main(String[] args){
    int[] bubbles = {5,3,2,4,6};
    boolean swapped = true;
    for(int i = bubbles.length - 1; i > 0 && swapped; i--){
	swapped = false;
        for(int j = 0; j < i; j++){
	    if(bubbles[j] > bubbles[j+1]){
		int temp = bubbles[j];
		bubbles[j] = bubbles[j+1];
		bubbles[j+1] = temp;
		swapped = true;
            }
        }
    }
}

在最好的情况下，改进后的算法时间复杂度为 O(n) 。