冒泡排序
冒牌排序有三种常见的书写方法,这里介绍第一种和第三种(第二种方法的提炼和修改)
冒泡排序中用到了值交换,这里建议以后都是用位运算来实现值交换,不懂的自己可以去搜百度为什么这样可以实现值交换
public static void swap(int a[],int c,int d){ a[c] = a[c]^a[d]; a[d]= a[c]^a[d]; a[c]=a[c]^a[d]; }
冒泡排序第一种是最常见的方法:时间复杂度为o(n^2)
int c [] = {1,5,6,8,7,6,3,1}; for(int i =0;i<c.length-1;i++){ for (int j = 0;j<c.length-1-i;j++){ swap(c,j,j+1); } }
冒泡排序第三种方法优化了时间复杂度,最大可优化为o(n)
int c [] = {1,5,6,8,7,6,3,1}; boolean swapped =true; int index = c.length-1; int indexlast = -1; while(swapped){ swapped = false; for (int i = 0;i< index;i++){ if(c[i]>c[i+1]){ swap(c,i,i+1); } swapped = true; indexlast = i; } index = indexlast; }