氣泡排序法(Bubble Sort)演算法，容易實作的穩定排序演算法

氣泡排序(Selection Sort)演算法又稱為泡沫排序演算法，是基本的排序演算法，是學習程式語言最先需要學會的排序演算法之一。顧名思義，就是它的排序方式如同氣泡一般，不斷將最大的元素擠出(移動)到序列最尾端，當所有元素都被被擠出後，排序就完成了！而且排序結果是穩定的。

氣泡排序法(Bubble Sort)

氣泡排序法的概念

氣泡排序法會從序列最前方開始進行走訪，在每次迭代時，會拿當前索引位置的元素與其下一個索引位置的元素進行比較，如果下一個元素比較小，就進行交換；如果下一個元素沒有比較小，就不進行交換。當序列被走訪完一次之後，序列的最尾端元素即為最大的元素。再來重新走訪一次序列，用同樣的方法將第二大的元素值擠進序列的從尾端開始倒數的第二個位置。然後重新走訪一次序列，用同樣的方法將第三大的元素值擠進序列的從尾端開始倒數的第三個位置。依此類推，直到所有元素都被擠到尾端，或是在走訪序列的過程中，如果發現都沒有元素被交換的話，表示此時的序列已經完成排序了。

氣泡排序法的過程

假設現在有個陣列資料，內容如下：

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢？

一開始，要將重點聚焦於陣列最尾端的位置，因為我們要先將整個陣列的最大值移動到陣列的最尾端。

從陣列最前方開始，逐次兩兩比較元素的大小，將兩個元素中較大的元素排在後面，即可逐漸將最大的元素從陣列前方擠到陣列後方。這就像是沉在水中的大氣泡，像要漂浮到水面上前，必須擠開其它的小氣泡一樣。

所以，若要擠出陣列的最大值至陣列的最尾端，位於陣列最前端的的69，要跟它之後的元素81比大小，如下表：

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

由於69比81小，所以不用換位置。然後再比81和30的大小，如下表：

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
           └┬┘
          81 > 30

81比30大，所以81會擠開30，與30交換，排在30之後。

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  81  38   9   2  47  61  32  79
           └─┘

然後再比較81和38的大小，如下表：

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  81  38   9   2  47  61  32  79
               └┬┘
              81 > 38

81比38大，所以81會擠開38，與38交換，排在38之後。

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38  81   9   2  47  61  32  79
               └─┘

繼續判斷大小並移動，直到最大值被擠到陣列最尾端：

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38  81   9   2  47  61  32  79
                   └┬┘
                  81 > 9

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9  81   2  47  61  32  79
                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9  81   2  47  61  32  79
                       └┬┘
                      81 > 2

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  81  47  61  32  79
                       └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  81  47  61  32  79
                           └┬┘
                          81 > 47

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  81  61  32  79
                           └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  81  61  32  79
                               └┬┘
                              81 > 61

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  81  32  79
                               └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  81  32  79
                                   └┬┘
                                  81 > 32

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  81  79
                                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  81  79
                                       └┬┘
                                      81 > 79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  79  81
                                       └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  79  81

如此一來，陣列中的最大元素81就成功被擠出至最尾端了。接著用同樣的方法繼續找出第二大的元素，並將其擠出至從尾端開始倒數的第二個位置，再找出第三大的元素，並將其擠出從尾端開始倒數的第三個位置。直到所有元素都被擠出為止，陣列就排序完成了！完整過程如下：

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79
           └┬┘
          81 > 30

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  81  38   9   2  47  61  32  79
           └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  81  38   9   2  47  61  32  79
               └┬┘
              81 > 38

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38  81   9   2  47  61  32  79
               └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38  81   9   2  47  61  32  79
                   └┬┘
                  81 > 9

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9  81   2  47  61  32  79
                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9  81   2  47  61  32  79
                       └┬┘
                      81 > 2

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  81  47  61  32  79
                       └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  81  47  61  32  79
                           └┬┘
                          81 > 47

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  81  61  32  79
                           └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  81  61  32  79
                               └┬┘
                              81 > 61

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  81  32  79
                               └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  81  32  79
                                   └┬┘
                                  81 > 32

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  81  79
                                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  81  79
                                       └┬┘
                                      81 > 79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  79  81
                                       └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  79  81

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   69  30  38   9   2  47  61  32  79  81
       └┬┘
      69 > 30

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  69  38   9   2  47  61  32  79  81
       └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  69  38   9   2  47  61  32  79  81
           └┬┘
          69 > 38

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  69   9   2  47  61  32  79  81
           └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38  69   9   2  47  61  32  79  81
               └┬┘
              69 > 9

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9  69   2  47  61  32  79  81
               └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9  69   2  47  61  32  79  81
                   └┬┘
                  69 > 2

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  69  47  61  32  79  81
                   └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  69  47  61  32  79  81
                       └┬┘
                      69 > 47

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  69  61  32  79  81
                       └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  69  61  32  79  81
                           └┬┘
                          69 > 61

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  69  61  32  79  81
                           └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  69  32  79  81
                               └┬┘
                              69 > 32

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  32  69  79  81
                               └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  32  69  79  81
                                   └┬┘
                                  69 < 79

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  32  69  79  81

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  32  69  79  81
       └┬┘
      30 < 38

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30  38   9   2  47  61  32  69  79  81
           └┬┘
          38 > 9

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9  38   2  47  61  32  69  79  81
           └─┘

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9  38   2  47  61  32  69  79  81
               └┬┘
              38 > 2

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  61  32  69  79  81
               └─┘

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  61  32  69  79  81
                   └┬┘
                  38 < 47

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  61  32  69  79  81
                       └┬┘
                      47 < 61

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  61  32  69  79  81
                           └┬┘
                          61 > 32

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  32  61  69  79  81
                           └─┘

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  32  61  69  79  81
                               └┬┘
                              61 < 69

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  32  61  69  79  81

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值   30   9   2  38  47  32  61  69  79  81
       └┬┘
      30 > 9

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30   2  38  47  32  61  69  79  81
       └─┘

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9  30   2  38  47  32  61  69  79  81
           └┬┘
          30 > 2

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  47  32  61  69  79  81
           └─┘

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  47  32  61  69  79  81
               └┬┘
              30 < 38

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  47  32  61  69  79  81
                   └┬┘
                  38 < 47

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  47  32  61  69  79  81
                       └┬┘
                      47 > 32

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  32  47  61  69  79  81
                       └─┘

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  32  47  61  69  79  81
                           └┬┘
                          47 < 61

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  32  47  61  69  79  81

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    9   2  30  38  32  47  61  69  79  81
       └┬┘
       9 > 2

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  32  47  61  69  79  81
       └─┘

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  32  47  61  69  79  81
           └┬┘
           9 < 30

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  32  47  61  69  79  81
               └┬┘
               30 < 38

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  38  32  47  61  69  79  81
                   └┬┘
                   38 > 32

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                   └─┘

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                       └┬┘
                       38 < 47

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
       └┬┘
       2 < 9

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
           └┬┘
           9 < 30

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
               └┬┘
               30 < 32

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                   └┬┘
                   32 < 38

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                       ※

氣泡排序法的程式實作

/// 氣泡排序法(遞增)。
pub fn bubble_sort(array: &mut [i32]) {
    for i in (1..array.len()).rev() {
        let mut sorted = true;

        for j in 0..i {
            let jj = j + 1;

            if array[j] > array[jj] {
                array.swap(j, jj);

                sorted = false;
            }
        }

        if sorted {
            break;
        }
    }
}

/// 氣泡排序法(遞減)。
pub fn bubble_sort_desc(array: &mut [i32]) {
    for i in (1..array.len()).rev() {
        let mut sorted = true;

        for j in 0..i {
            let jj = j + 1;

            if array[j] < array[jj] {
                array.swap(j, jj);

                sorted = false;
            }
        }

        if sorted {
            break;
        }
    }
}

/**
 * 氣泡排序法(遞增)。
 */
public static void bubbleSort(final int[] array) {
    for (int i = array.length - 1; i > 0; --i) {
        boolean sorted = true;

        for (int j = 0; j < i; ++j) {
            final int jj = j + 1;

            if (array[j] > array[jj]) {
                final int temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }
    }
}

/**
 * 氣泡排序法(遞減)。
 */
public static void bubbleSortDesc(final int[] array) {
    for (int i = array.length - 1; i > 0; --i) {
        boolean sorted = true;

        for (int j = 0; j < i; ++j) {
            final int jj = j + 1;

            if (array[j] < array[jj]) {
                final int temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }
    }
}

/**
 * 氣泡排序法(遞增)。
 */
function bubbleSort(array: number[]) {
    for (let i = array.length - 1;i > 0;i--) {
        let sorted = true;

        for (let j = 0;j < i;j++) {
            const jj = j + 1;

            if (array[j] > array[jj]) {
                const temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }
    }
}

/**
 * 氣泡排序法(遞減)。
 */
function bubbleSortDesc(array: number[]) {
    for (let i = array.length - 1;i > 0;i--) {
        let sorted = true;

        for (let j = 0;j < i;j++) {
            const jj = j + 1;

            if (array[j] < array[jj]) {
                const temp = array[j];
                array[j] = array[jj];
                array[jj] = temp;

                sorted = false;
            }
        }

        if (sorted) {
            break;
        }
    }
}

// 氣泡排序法(遞增)。
func BubbleSort(array []int) {
	for i := len(array) - 1; i > 0; i -= 1 {
		sorted := true

		for j := 0; j < i; j += 1 {
			jj := j + 1

			if array[j] > array[jj] {
				array[j], array[jj] = array[jj], array[j]

				sorted = false
			}
		}

		if sorted {
			break
		}
	}
}

// 氣泡排序法(遞減)。
func BubbleSortDesc(array []int) {
	for i := len(array) - 1; i > 0; i -= 1 {
		sorted := true

		for j := 0; j < i; j += 1 {
			jj := j + 1

			if array[j] < array[jj] {
				array[j], array[jj] = array[jj], array[j]

				sorted = false
			}
		}

		if sorted {
			break
		}
	}
}

氣泡排序法的複雜度