簡介

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

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

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

流程示意圖:  

bs    

實作上直接使用迭代法迴圈就可以很容易的完成。另外可以使用額外的旗標(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;
    }

}

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()