冒泡排序的最差时间复杂度为o(n^2),最好时间复杂度为o(n)
1.首先,按照传统的算法实现
for(int i=arr.length-1;i>0;i--) for(int j=0;j<i;j++) { if(arr[j]>arr[j+1]) swap(arr,j,j+1); }
2.从这段代码分析,当数组本身为有序数组时,时间复杂度仍为o(n^2);所以需要对代码优化。
boolean flag; for(int i=arr.length-1;i>0;i--) { flag=false; for(int j=0;j<i;j++) { if(arr[j]>arr[j+1]) { swap(arr,j,j+1); flag=true; } } if(flag==false) break; }
也就是当进行第一轮比较时,如果没有发生交换情况,直接跳出循环,所以就进行了一次比较,故此时的时间复杂度为o(n)