冒泡排序
冒泡排序的最差时间复杂度为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)
查看18道真题和解析