java排序之冒泡排序

java冒泡排序（Bubble Sort）是一種計較機科學范疇的較簡單的排序算法。

根基概念：

依次比力相鄰的兩個數，將小數放在前面，大數放在后面。即在第一趟：起首比力第1個和第2個數，將小數放前，大數放后。然后比力第2個數和第3個數，將小數放前，大數放后，如斯繼續，直至比力最后兩個數，將小數放前，大數放后。至此第一趟竣事，將最大的數放到了最后。在第二趟：仍從第一對數起頭比力（因為可能因為第2個數和第3個數的互換，使得第1個數不再小于第2個數），將小數放前，大數放后，一向比力到倒數第二個數（倒數第一的位置上已經是最大的），第二趟竣事，在倒數第二的位置上獲得一個新的最大數（其其實整個數列中是第二大的數）。如斯下去，反復以上過程，直至最終完當作排序。

東西/原料

電腦
myeclipse

第一步：數據對象的冒泡排序。

1
用二重輪回實現，外輪回變量設為i，內輪回變量設為j。假若有n個數需要進行排序，則外輪回反復n-1次，內輪回依次反復n-1，n-2，...，1次。每次進行比力的兩個元素都是與內輪回j有關的，它們可以別離用a[j]和a[j+1]標識，i的值依次為1,2,...,n-1，對于每一個i，j的值依次為0,1,2,...n-i 。
代碼如下所示：
import java.util.Arrays;

public class Test {

public static void arraySort(int[] arr) {
int temp;// 界說一個姑且變量
for (int i = 0; i < arr.length - 1; i++) {// 冒泡趟數
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j + 1] < arr[j]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

public static void main(String[] args) {
int arr[] = new int[] { 9, 6, 3, 2, 3, 4 };
arraySort(arr);
System.out.println(Arrays.toString(arr));
}
}
2
機能闡發（執行效率闡發）：
若記實序列的初始狀況為"正序"，則冒泡排序過程只需進行一趟排序，在排序過程中只需進行n-1次比力，且不移動記實；反之，若記實序列的初始狀況為"逆序"，則需進行n(n-1）/2次比力和記實移動。是以冒泡排序總的時候復雜度為O(n*n)。
3
機能優化冒泡排序
1、舉個例子：int[] array = {2,4,9,7,6,5};
第一輪2和4進行比力，2<4，位置不變。再4和9進行比力，4<9，位置不變。再9和7進行比力，9>7，9和7的位置交換。再9和6進行比力，9>6，9和6的位置交換。再9和5進行比力，9>5，位置交換。第一輪比力的成果就是2 4 7 6 5 9。
第二輪2和4進行比力，2<4，位置不變。再4和7進行比力，4<7，位置不變。再7和5進行比力，7>6，7和6的位置交換。再7和5進行比力，7>5，7和5的位置交換。第二輪的成果就是2 4 6 5 7 9。
第三輪2和4進行比力，2<4，位置不變。再4和6進行比力，4<6，位置不變。再6和5進行比力，6>5，6和5的位置交換。第三輪的成果是2 4 5 6 7 9（已經是我們想要的成果了）。
2、具體代碼如下所示：
import java.util.Arrays;

public class Test {

public static void arraySort(int[] arr) {
int temp;// 界說一個姑且變量
for (int i = 0; i < arr.length - 1; i++) {// 冒泡趟數，n-1趟
boolean flag = true;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j + 1] < arr[j]) {
flag = false;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

}
}

// 若是當輪沒有發生位置轉變，申明已經排序完畢，就沒有需要再進行輪回了
if (flag) {
break;
}
}
}

public static void main(String[] args) {
int arr[] = new int[] { 2, 4, 9, 7, 6, 5 };
arraySort(arr);
System.out.println(Arrays.toString(arr));
}
}

第二步：實體對象的冒泡排序。

1
前面我們說了一下簡單的根基數據類型的排序。下面我們解決一個實體的多前提排序。
插手有一個圓柱實體類：Column 此刻我們需要按照其半徑radius從小到大排序，若是半徑一致，則按照高h從小到大排序。
2
實體類：Column

public class Column implements Comparable<Object> {
private int radius;
private int h;

public Column() {
};

public Column(int radius, int h) {
this.radius = radius;
this.h = h;
};

@Override
public String toString() {
return "Column{" + "radius=" + radius + ", h=" + h + '}';
}

@Override
public int compareTo(Object o) {
return 0;
}

public int getRadius() {
return radius;
}

public void setRadius(int radius) {
this.radius = radius;
}

public int getH() {
return h;
}

public void setH(int h) {
this.h = h;
}
}
3
測試類如下：
public class ColumnTest {
public static void main(String[] args) {
Column co1 = new Column(5, 3);
Column co2 = new Column(2, 4);
Column co3 = new Column(4, 3);
Column co4 = new Column(2, 3);
Column co5 = new Column(4, 6);
Column[] arry = { co1, co2, co3, co4, co5 };
testArraySort(arry);
}

private static void testArraySort(Column[] arry) {
Column cnj;
// 利用冒泡排序
for (int i = 0; i < arry.length - 1; i++) {
for (int j = 0; j < arry.length - 1 - i; j++) {
cnj = arry[j];
if (arry[j + 1].getRadius() < cnj.getRadius()
|| (cnj.getRadius() == arry[j + 1].getRadius() && arry[j + 1].getH() < cnj.getH())) {
arry[j] = arry[j + 1];
arry[j + 1] = cnj;
}
}
}
// 打印輸出
for (int i = 0; i < arry.length; i++) {
System.out.print("(" + arry[i].getRadius() + "," + arry[i].getH() + ") ");
}
}

}
4
效率晉升利用優化后的體例：
package com.sgg.test;

public class ColumnTest {
public static void main(String[] args) {
Column co1 = new Column(5, 3);
Column co2 = new Column(2, 4);
Column co3 = new Column(4, 3);
Column co4 = new Column(2, 3);
Column co5 = new Column(4, 6);
Column[] arry = { co1, co2, co3, co4, co5 };
testArraySort(arry);
}

private static void testArraySort(Column[] arry) {
Column cnj;
// 利用冒泡排序
for (int i = 0; i < arry.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < arry.length - 1 - i; j++) {
cnj = arry[j];
if (arry[j + 1].getRadius() < cnj.getRadius()
|| (cnj.getRadius() == arry[j + 1].getRadius() && arry[j + 1].getH() < cnj.getH())) {
flag = false;
arry[j] = arry[j + 1];
arry[j + 1] = cnj;
}
}

// 若是當輪沒有發生位置轉變，申明已經排序完畢，就沒有需要再進行輪回了
if (flag) {
break;
}
}
// 打印輸出
for (int i = 0; i < arry.length; i++) {
System.out.print("(" + arry[i].getRadius() + "," + arry[i].getH() + ") ");
}
}

}