冒泡排序(Bubble Sort)权逗，是計(jì)算機(jī)科學(xué)領(lǐng)域一種較簡(jiǎn)單的排序算法罐呼。
冒泡排序會(huì)重復(fù)地走訪過(guò)要排序的元素?cái)?shù)列凰萨，依次比較兩個(gè)相鄰的元素，如果順序錯(cuò)誤(如從大到小械馆、首字母從Z到A)就把它們交換過(guò)來(lái)胖眷。
走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說(shuō)該元素列已經(jīng)排序完成霹崎。
時(shí)間復(fù)雜度：O(n^2)
排序方式：原地排序
普通冒泡排序
普通冒泡排序共需要進(jìn)行n-1趟排序珊搀，每趟進(jìn)入n-1-i次比較(交換)，代碼實(shí)現(xiàn)如下：
/**
* 冒泡排序(升序)
*/
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
int item1 = array[j];
int item2 = array[j + 1];
if (item1 > item2) {
array[j] = item2;
array[j + 1] = item1;
}
}
}
}
優(yōu)化冒泡排序
在普通冒泡排序的基礎(chǔ)上尾菇，若我們發(fā)現(xiàn)一趟排序中沒(méi)有發(fā)生任何交換境析，則說(shuō)明數(shù)組排序已完成囚枪。
/**
* 優(yōu)化冒泡排序(升序)
*/
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
boolean swap = false;
for (int j = 0; j < array.length - 1 - i; j++) {
int item1 = array[j];
int item2 = array[j + 1];
if (item1 > item2) {
array[j] = item2;
array[j + 1] = item1;
swap = true;
}
}
if (!swap) { // 未發(fā)生交換，說(shuō)明排序完成
System.out.println("排序完成" + i + "/" + array.length);
break;
}
}
}
