定義
冒泡排序 Bubble Sort 是一種簡(jiǎn)單的排序算法儡遮。
它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換休建，也就是說(shuō)該數(shù)列已經(jīng)排序完成乍恐。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢 “浮” 到數(shù)列的頂端。
冒泡排序?qū)?n 個(gè)項(xiàng)目需要 O( n^2) 的比較次數(shù)测砂，且可以原地排序茵烈。盡管這個(gè)算法是最簡(jiǎn)單了解和實(shí)現(xiàn)的排序算法之一，但它對(duì)于包含大量的元素的數(shù)列排序是很沒(méi)有效率的砌些。
排序過(guò)程
冒泡排序算法的運(yùn)作如下：
- 比較相鄰的元素瞧毙。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)寄症。
- 對(duì)每一對(duì)相鄰元素作同樣的工作宙彪，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后有巧，最后的元素會(huì)是最大的數(shù)释漆。
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)篮迎。
- 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟男图，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
/**
* 冒泡排序是最簡(jiǎn)單的排序之一了甜橱，其大體思想就是通過(guò)與相鄰元素的比較和交換來(lái)把小的數(shù)交換到最前面逊笆。
* 這個(gè)過(guò)程類似于水泡向上升一樣，因此而得名岂傲。
* <p>
* 舉個(gè)栗子难裆，對(duì) 5,3,8,6,4 這個(gè)無(wú)序序列進(jìn)行冒泡排序。
* 首先從后向前冒泡镊掖，4 和 6 比較乃戈，把 4 交換到前面，序列變成 5,3,8,4,6亩进。
* 同理 4 和 8 交換症虑，變成 5,3,4,8,6,
* 3 和 4 無(wú)需交換。
* 5 和 3 交換归薛，變成 3,5,4,8,6,3.
* 這樣一次冒泡就完了谍憔，把最小的數(shù) 3 排到最前面了。
* <p>
* 對(duì)剩下的序列依次冒泡就會(huì)得到一個(gè)有序序列主籍。
* 冒泡排序的時(shí)間復(fù)雜度為 O(n^2)习贫。
*
* @author wb
*/
public class BubbleSort {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
//rightToLeftSort(arr);
leftToRight(arr);
}
//從左往右冒泡
private static void leftToRight(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j + 1, j);
}
}
}
}
//從右往左冒泡
private static void rightToLeftSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j - 1, j);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
白話分析：
- 從第一個(gè)元素循環(huán)遍歷整個(gè)數(shù)組，挨個(gè)比較相鄰的兩個(gè)元素崇猫，如果兩者不是期望的排序沈条，那么就移動(dòng)交換兩者需忿，直至數(shù)組結(jié)尾诅炉；
- 一輪比較交換之后蜡歹，最大數(shù)字被交換到末尾即數(shù)組的頂端。
- 重復(fù)步驟1涕烧，比較除上一輪結(jié)尾數(shù)字之外的數(shù)組
- 直至數(shù)組剩余最后一個(gè)數(shù)字月而，此時(shí)排序完成木缝；
冒泡排序.gif
