氣泡排序法(Bubble Sort)

文章已搬家，請點擊前往👈

REDIRECT_MODE = 1;

簡介

氣泡排序法(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 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 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 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 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

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 array[j + 1]) swap(array[j], array[j + 1]); }

旗標版本

FlagBubbleSort.h

#ifndef FLAGBUBBLESORT_H #define FLAGBUBBLESORT_H

#include

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 array[j + 1]) { swap(array[j], array[j + 1]); swapped = true; } if(!swapped) break; }

}

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

-->

小殘的程式光廊

提供一些演算法、資料結構、程式題目的整理與說明，PHP和JavaScript的基本教學和一些程式相關問題與解法。

氣泡排序法(Bubble Sort)

參觀人氣

熱門文章

文章分類

電腦程式 (10)

最新文章

文章搜尋

文章精選