演算法 - 氣泡排序法 (Bubble Sort)

簡介

氣泡排序法 (Bubble Sort) 是最容易理解和實作的一種排序演算法，也翻譯作冒泡排序法。由於它很容易學習，所以也是許多演算法課程中第一個學習的排序演算法。

由於他的演算法過程會將最大的數值移動到陣列最後面，而較小的數值則逐漸的往陣列前端移動，就像有許多氣泡慢慢從底部浮出，因此稱為氣泡排序法。他的運作流程如下：

比較相鄰的兩個元素，若前面的元素較大就進行交換。
重複進行 1 的動作直到最後面，最後一個元素將會是最大值。
重複進行 1, 2 的動作，每次比較到上一輪的最後一個元素。
重複進行以上動作直到沒有元素需要比較。

流程示意圖：

實作上直接使用迴圈就可以很容易的完成。另外可以使用額外的旗標 (Flag) 來判斷這一輪是否有發生交換情形，若都沒有發生交換表示數列已經是排序好的，即可跳出迴圈，因此最佳時間複雜度是有可能達到 O(n)。

分析

最佳時間複雜度：O(n)
平均時間複雜度：O(n^2)
最差時間複雜度：O(n^2)
空間複雜度：O(1)
Stable sort：是

虛擬碼

一般版本

function sort(list)
	// 重複 N 次
	for i = 0 to list.length - 1
		// 比較到上一輪最後一個
		for j = 0 to list.length - i - 1
			if list[j] > list[j+1]
				swap (list[j], list[j+1])
			end if
		end for
	end for
end function

旗標版本

function sort(list)
	// 重複N次
	for i = 0 to list.length - 1
		var swapped = false
		//比較到上一輪最後一個
		for j = 0 to list.length - i - 1
			if list[j] > list[j+1]
				swap (list[j], list[j+1])
				swapped  = true
			end if
		end for
		if !swapped
			break
		end if
	end for
end function

語法

C#

一般版本

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BubbleSort
{
    class BubbleSort
    {
        public static void Sort(int[] array)
        {
            for (int i = array.Length - 1; i > 0; --i)
                for (int j = 0; j < i; ++j)
                    if (array[j] > array[j + 1])
                        Swap(array, j, j + 1);
        }

        private static void Swap(int[] array, int indexA, int indexB)
        {
            int tmp = array[indexA];
            array[indexA] = array[indexB];
            array[indexB] = tmp;
        }
    }
}

旗標版本

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BubbleSort
{
    class FlagBubbleSort
    {
        public static void Sort(int[] array)
        {
            for (int i = array.Length - 1; i > 0; --i)
            {
                bool swapped = false;
                for (int j = 0; j < i; ++j)
                    if (array[j] > array[j + 1])
                    {
                        Swap(array, j, j + 1);
                        swapped = true;
                    }
                if (!swapped)
                    break;
            }
        }

        private static void Swap(int[] array, int indexA, int indexB)
        {
            int tmp = array[indexA];
            array[indexA] = array[indexB];
            array[indexB] = tmp;
        }
    }
}

Java

一般版本

public class BubbleSort {
    public static void Sort(int[] array)
    {
        for (int i = array.length - 1; i > 0; --i)
            for (int j = 0; j < i; ++j)
                if (array[j] > array[j + 1])
                    Swap(array, j, j + 1);
    }

    private static void Swap(int[] array, int indexA, int indexB)
    {
        int tmp = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = tmp;
    }
}

旗標版本

public class FlagBubbleSort {
    public static void Sort(int[] array)
    {
        for (int i = array.length - 1; i > 0; --i)
        {
            boolean swapped = false;
            for (int j = 0; j < i; ++j)
                if (array[j] > array[j + 1])
                {
                    Swap(array, j, j + 1);
                    swapped = true;
                }
            if(!swapped)
                break;
        }
    }

    private static void Swap(int[] array, int indexA, int indexB)
    {
        int tmp = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = tmp;
    }
}

C++

一般版本

BubbleSort.h

#ifndef BUBBLESORT_H
#define BUBBLESORT_H

#include <algorithm>

using namespace std;

class BubbleSort
{
    public:
        static void Sort(int* array, int length);
    protected:
    private:
};

#endif // BUBBLESORT_H

BubbleSort.cpp

#include "BubbleSort.h"

void BubbleSort::Sort(int* array, int length)
{
    for (int i = length - 1; i > 0; --i)
        for (int j = 0; j < i; ++j)
            if (array[j] > array[j + 1])
                swap(array[j], array[j + 1]);
}

旗標版本

FlagBubbleSort.h

#ifndef FLAGBUBBLESORT_H
#define FLAGBUBBLESORT_H

#include <algorithm>

using namespace std;

class FlagBubbleSort
{
    public:
        static void Sort(int* array, int length);
    protected:
    private:
};

#endif // FLAGBUBBLESORT_H

FlagBubbleSort.cpp

#include "FlagBubbleSort.h"

void FlagBubbleSort::Sort(int* array, int length)
{
    for (int i = length - 1; i > 0; --i)
    {
        bool swapped = false;
        for (int j = 0; j < i; ++j)
            if (array[j] > array[j + 1])
            {
                swap(array[j], array[j + 1]);
                swapped = true;
            }
        if(!swapped)
            break;
    }
}