[toc]
冒泡排序
程序代码packagecom.uplooking.bigdata.datastructure;importjava.util.Arrays;publicclassBubbleSort{publicstaticvoidmain(String[]args){int[]arr={8,-2,3,9,0,1,7,6};System.out.println("排序前："+Arrays.toString(arr));bubbleSort(arr);System.out.println("排序后："+Arrays.toString(arr));}/***排序过程分析：*i前比较次数(arr.length为8)*开始：8,-2,3,9,0,1,7,6**第1趟结束：-2,3,8,0,1,7,6,907**第2趟结束：-2,3,0,1,7,6,8,916**第3趟结束：-2,0,1,3,6,7,8,925**第4趟结束：-2,0,1,3,6,7,8,934**第5趟结束：-2,0,1,3,6,7,8,943**第6趟结束：-2,0,1,3,6,7,8,952**第7趟结束：-2,0,1,3,6,7,8,961**结论：需要比较的趟数为arr.length-1*每一趟需要比较arr.length-1-i次**由于冒泡排序为相邻两者相互比较对调，并不会更改其原本排序的顺序，所以是稳定排序法*/publicstaticvoidbubbleSort(int[]arr){for(inti=0;iarr[j+1]){swap(arr,j,j+1);}}}}publicstaticvoidswap(int[]arr,inti,intj){arr[i]=arr[i]^arr[j];arr[j]=arr[i]^arr[j];arr[i]=arr[i]^arr[j];}}
测试排序前：[8,-2,3,9,0,1,7,6]排序后：[-2,0,1,3,6,7,8,9]
时间复杂度分析1.可以看到，将比较次数相加起来(等差数列)，其时间复杂度为O(n^2)2.由于冒泡排序为相邻两者相互比较对调，并不会更改其原本排序的顺序，所以是稳定排序法
