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() + ") ");
}
}

}