/**
* @author jy
* @date 2018年6月7日
* <p>Description: </p>
*/
package sort;
import java.util.Arrays;
/**
* @author jy
*/
public class BubbleSort {
public void bubbleSort(int a[]) {
// 长度为n的数组，只需要n-1趟
// 两两比较，大的就放在最后
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
/**
* @param a
* @param j
* @param i
* <p>
* Description:
* </p>
*/
private void swap(int[] a, int j, int i) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* @param args
* <p>
* Description:
* </p>
*/
public static void main(String[] args) {
int a[] = { 8, 61, 1, 9, 6 };
BubbleSort s = new BubbleSort();
s.bubbleSort(a);
System.out.println(Arrays.toString(a));
}
}
通过从左到右不断交换相邻逆序的相邻元素，在一轮的交换之后，可以让未排序的元素上浮到最右侧，是的右侧是已排序的。
一次数据比较和交换算一次，共需n-1+(n-2)+...+1=n(n-1)/2 。故时间复杂度为O（n^2）
优化：如果在中间的某一步已经有序了，不需要再继续遍历了。
public void bubbleSort(int a[]) {
// 长度为n的数组，只需要n-1趟
// 两两比较，大的就放在最后
boolean flag=false;
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
flag=true;
}
}
if(flag==false){
System.out.println("break");
break;
}
}
}
