Java常見排序演算法詳解——氣泡排序

摘要： 轉載請註明出處：[ https://www.jianshu.com/p/df900e6ddbac 我們在面試的時候時常會問到我們演算法題，而演算法題當中排序演算法題是問到最多的。應廣大同學的建議，我特意整理了一下Java常見的排序演算法，我儘量從概念，原理，程式碼這幾方面詳細闡述旨在讓...

轉載請註明出處：[ https://www.jianshu.com/p/df900e6ddbac

我們在面試的時候時常會問到我們演算法題，而演算法題當中排序演算法題是問到最多的。應廣大同學的建議，我特意整理了一下Java常見的排序演算法，我儘量從概念，原理，程式碼這幾方面詳細闡述旨在讓大家知道、理解、應用。

氣泡排序Bubble Sort

概念：氣泡排序是一種交換排序，它的基本思想是：

兩兩比較相鄰記錄，如果反序則交換，直到沒有反序的記錄為止。

原理：

例如我們有一個數組，我們如果需要把較大的元素排在前面，把小的元素排在後面，那麼需要從尾部到頭開始比較操作：

1. 從尾部開始比較相鄰的兩個元素，如果尾部的元素比前面的大，就交換兩個元素的位置。
2. 往前對每個相鄰的元素都做這樣的比較、交換操作，這樣到陣列頭部時，第 1 個元素會成為最大的元素。
3. 重新從尾部開始第 1、2 步的操作，除了在這之前頭部已經排好的元素。
4. 繼續對越來越少的資料進行比較、交換操作，直到沒有可比較的資料為止，排序完成。

可能看到這，有的同學還不是很明白，那麼我們假如，現在有這麼幾個數字 11 10 5 7 4 29 這麼幾個數字運用氣泡排序從大到小排序。

我們可以看到目前，我們的陣列起始狀態如下：

位置	數字
0	11
1	10
2	5
3	7
4	4
5	29

29和4比較，29比4大，那麼29和4進行交換那麼交換之後，陣列狀態如下：

位置	數字
0	11
1	10
2	5
3	7
4	29
5	4

29和7比較，29比7大，那麼29和7進行交換

那麼交換之後，陣列狀態如下：

位置	數字
0	11
1	10
2	5
3	29
4	7
5	4

29和5比較，29比5大，那麼29和5進行交換

那麼交換之後，陣列狀態如下：

位置	數字
0	11
1	10
2	29
3	5
4	7
5	4

29和10比較，29比10大，那麼29和10進行交換

那麼交換之後，陣列狀態如下：

位置	數字
0	11
1	29
2	10
3	5
4	7
5	4

29和11比較，29比11大，那麼29和11進行交換

那麼交換之後，陣列狀態如下：

位置	數字
0	29
1	11
2	10
3	5
4	7
5	4

我們可以看到，經過第一趟的排序之後。我們已經找到了最大的元素，並且把最大的數字29排到了0位置，這個表象就像水氣泡從水底冒上來一樣，所以形象的成為“氣泡排序”

接下來，我們再看看第二趟陣列是怎麼變化的

第二趟初始化的陣列

位置	數字
0	29
1	11
2	10
3	5
4	7
5	4

4和7比較，4沒有7大，那麼不變

7和5比較，7比5大，那麼7和5進行交換

位置	數字
0	29
1	11
2	10
3	7
4	5
5	4

7和10比較，7沒有10大，那麼不變

10和11比較，10沒有11大，那麼不變

那麼經過第二趟結束之後，陣列最後為

位置	數字
0	29
1	11
2	10
3	7
4	5
5	4

我們可以看到經過兩趟之後，我們的陣列就按照我們的要求從大到小排好了。

因此，假如有N個元素，最好的情況我們僅僅需要N-1次比較和交換，最壞的情況下需要N（N-1）/2次比較和交換才能完成。

程式碼實現：

Java實現

/**
 * @author yangzc
 * @data 2019/4/8 22:21
 * @desc 氣泡排序
 */
public class BubbleSort {
private int[] array;

public BubbleSort(int[] array) {
this.array = array;
}

/**
* 從小到大
*/
public void sort() {
int length = array.length;
if (length > 0) {
for (int i = 1; i < length; i++) {
for (int j = 0; j < length - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
}

/**
* 從大到小
*/
public void sort2() {
int length = array.length;
if (length > 0) {
for (int i = length - 1; i > 0; i--) {
for (int j = length - 1; j > length - 1 - i; j--) {
if (array[j] > array[j - 1]) {
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
}
}
}

Java和Kotlin程式碼我均放在了GitHub上，歡迎Star！

GitHub地址： https://github.com/yang0range/MyAlgorithm

歡迎關注公共號

關注公共號會有更多收穫！