算法入门学习----1.1冒泡排序

你的名字 2022-06-01 05:38 139阅读 0赞

# 一、冒泡排序的原理 #

一个数组a\[\]有N个元素：

①第一次循环(**n-1**)

a\[0\]和a\[1\]进行比较，如果a\[0\]大于a\[1\],两者进行交换，否则不交换。

a\[1\]和a\[2\]进行比较，如果a\[1\]大于a\[2\],两者进行交换，否则不交换。

......................

a\[n-2\]和a\[**n-1**\]进行比较，如果a\[n-2\]大于a\[n-1\],两者进行交换，否则不交换。

②第二次循环(**n-2**)

a\[0\]和a\[1\]进行比较，如果a\[0\]大于a\[1\],两者进行交换，否则不交换。

a\[1\]和a\[2\]进行比较，如果a\[1\]大于a\[2\],两者进行交换，否则不交换。

......................

a\[n-3\]和a\[**n-2**\]进行比较，如果a\[n-3\]大于a\[n-2\],两者进行交换，否则不交换。

③第三次循环(n-3)

............

第n-1次循环（1）

a\[0\]和a\[1\]进行比较，如果a\[0\]大于a\[1\],两者进行交换，否则不交换。

# 二、冒泡排序时间复杂度和空间复杂度 #

时间复杂度：1+2+3+......(n-1)=n\*(n-1)/2 所以时间复杂度为 n^2

空间复杂度：①最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；  
②最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；  
③平均的空间复杂度为：O(1)；

# 三、冒泡排序代码的实现（Java） #

public class Maopao {
    	public static void main(String[] args){
    		int[] arr=new int[]{1,5,6,89,4,6,12,48,5,23};
    		maopao(arr);
    	}
    	public static void show(int[] arr){  //输出函数
    		for(int a: arr){
    			System.out.println(a);
    		}
    	}
    	public static void maopao(int[] arr){	
    		for(int n=arr.length-1;n > 0;n--){   //第一层，表示需要n-1次大循环
    			for(int m=0;m < n;m++){          //第二层，表示每次大循环需要多少次比较
    				if(arr[m] > arr[m+1]){
    					int temp =0;
    					temp = arr[m];
    					arr[m] = arr[m+1];
    					arr[m+1] = temp;
    				}
    			}
    		}
    		show(arr);
    	}
    }