目录
①比较相邻的元素，如果前一个元素比后一个元素大，则交换这两个元素的位置
②对每一对相邻的元素循环上面的步骤，最终最后面的元素就是最大值
冒泡排序的代码实现
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++){ if(greater(a[j],a[j+1])){ exchange(a,j,j+1); } } } } //比较v元素是否大于w元素 private static boolean greater(Comparable v,Comparable w){ return v.compareTo(w)>0; } //数组元素x和y交换位置 private static void exchange(Comparable[] a,int x,int y){ Comparable t=a[x]; a[x]=a[y]; a[y]=t; } } //测试代码 class Test{ public static void main(String[] args) { Integer[] a={4,5,6,3,2,1}; Bubble.sort(a); System.out.println(Arrays.toString(a)); } }
测试结果：
冒泡排序的时间复杂度分析
冒泡排序虽然采用了双层for循环遍历，但是真正完成排序的代码在内循环中，所以主要分析内层循环体的执行次数即可
在最坏的情况下。即数组为{6,5,4,3,2,1}的逆序
元素的比较次数为：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
元素的交换次数为：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
总执行次数为：2*(N^2/2-N/2)=N^2-N;
根据大O推导法则，保留最高阶项，即冒泡排序的时间复杂度为O(N^2)
第二种写法
public class BubbleSort { public static int[] bubbleSort(int[] arr, int len) { for (int i = 0; i < len; i++) { //确定排序趟数 for (int j = i + 1; j < len; j++) { //确定比较次数 if (arr[i] > arr[j]) { //交换 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } return arr; } public static void main(String[] args) { int[] arr = {1,28,3,21,11,7,6,18}; bubbleSort3(arr, arr.length); System.out.println(Arrays.toString(arr)); } }
