1 private static int[] bubbleSort(int[] arr) { 2 int k=arr.length-1,last=0; //最后一次交换的位置，后面已经为排好序状态 3 if (arr==null||arr.length<2) { 4 return arr; 5 } 6 for(int i=arr.length-1;i>=0;i--){ 7 boolean flag=false; //每次比较的时候都设置标志位，查看是否发送交换 8 for (int j = 0; j <k; j++) { 9 if (arr[j]>arr[j+1]) { 10 last=j; 11 swap(arr,j,j+1); 12 flag=true; //发生交换后，标志位变为true 13 } 14 } 15 k=last; 16 //如果标志位不发生变化，则说明已处于排好序的状态 17 if (!flag) { 18 return arr; 19 } 20 } 21 return arr; 22 } 23 private static void swap(int[] arr, int j, int i) { 24 int tmp=arr[j]; 25 arr[j]=arr[i]; 26 arr[i]=tmp; 27 } 28 29 private static int[] creatArray(int length,int range) { 30 if (length<1) { 31 return null; 32 } 33 int arr[]=new int[length]; 34 for(int i=0;i<length;i++){ 35 arr[i]=(int)(Math.random()*range); 36 } 37 return arr; 38 } 39 private static void show(int[] arr) { 40 if (arr.length<1||arr==null) { 41 return; 42 } 43 for(int i=0;i<arr.length;i++){ 44 System.out.print(arr[i]+" "); 45 } 46 System.out.println(); 47 } 48 public static void main(String[] args) { 49 for(int i=0;i<5;i++){ 50 show(bubbleSort(creatArray(10, 30))); 51 } 52 }
冒泡排序，为相邻两个元素进行比较，扫描的范围从0-N-1到1；时间复杂度为O（n方）
1 private static int[] bubbleSort(int[] arr) { 2 int k=arr.length-1,last=0; //最后一次交换的位置，后面已经为排好序状态 3 if (arr==null||arr.length<2) { 4 return arr; 5 } 6 for(int i=arr.length-1;i>=0;i--){ 7 boolean flag=false; //每次比较的时候都设置标志位，查看是否发送交换 8 for (int j = 0; j <k; j++) { 9 if (arr[j]>arr[j+1]) { 10 last=j; 11 swap(arr,j,j+1); 12 flag=true; //发生交换后，标志位变为true 13 } 14 } 15 k=last; 16 //如果标志位不发生变化，则说明已处于排好序的状态 17 if (!flag) { 18 return arr; 19 } 20 } 21 return arr; 22 }