排序:冒泡排序

16uni 2021年04月12日 637次浏览

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

举个栗子

基础版
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)