冒泡排序透過相鄰元素兩兩比較、交換,將最大(或最小)元素逐輪「冒泡」至陣列末端。雖時間複雜度為 O(n²),但邏輯直觀,適合教學與小規模資料。
using System;
namespace SortingDemo
{
///
/// 封裝排序演算法的類別,示範冒泡排序
///
public class SortingAlgorithms
{
private readonly int[] _array;
private int _count; // 實際元素數量
public SortingAlgorithms(int capacity)
{
_array = new int[capacity];
_count = 0;
}
/// 插入元素
public void Insert(int item)
{
if (_count >= _array.Length)
throw new InvalidOperationException("陣列已滿");
_array[_count++] = item;
}
/// 列印陣列內容
public void Display()
{
Console.WriteLine(string.Join(" ", _array, 0, _count));
}
///
/// 冒泡排序(由小到大)
/// 外層控制輪數,內層執行相鄰比較交換
///
public void BubbleSort()
{
// 優化:若某輪無交換,提前結束
for (int pass = 0; pass < _count - 1; pass++)
{
bool swapped = false;
// 每輪將最大值推至 _count - 1 - pass
for (int i = 0; i < _count - 1 - pass; i++)
{
if (_array[i] > _array[i + 1])
{
Swap(i, i + 1);
swapped = true;
}
}
if (!swapped) break; // 已有序
}
}
private void Swap(int i, int j)
{
int temp = _array[i];
_array[i] = _array[j];
_array[j] = temp;
}
}
}
class Program
{
static void Main()
{
var sorter = new SortingAlgorithms(10);
var rand = new Random(42); // 固定種子,結果可復現
for (int i = 0; i < 10; i++)
sorter.Insert(rand.Next(100)); // 0-99 隨機整數
Console.WriteLine("排序前:");
sorter.Display();
sorter.BubbleSort();
Console.WriteLine("排序後:");
sorter.Display();
Console.ReadKey();
}
}
排序前:
42 15 87 33 92 6 71 29 54 18
排序後:
6 15 18 29 33 42 54 71 87 92
| 指標 | 數值 | 說明 |
|---|---|---|
| 時間複雜度(最好) | O(n) | 資料已排序,啟用 swapped 優化 |
| 時間複雜度(平均/最差) | O(n²) | 雙層巢狀迴圈 |
| 空間複雜度 | O(1) | 原地排序,僅需常數額外空間 |
| 穩定性 | 穩定 | 相等元素不交換,相對順序不變 |
pass < n-1,內層 i < n-1-pass 避免重複比較已排序區swapped 標記,最佳情況降為 O(n)Swap 輔助方法提升可讀性void BubbleSort(T[] arr) where T : IComparable<T> 支援任意可比較型別冒泡排序雖非生產環境首選,但掌握其邊界控制與優化技巧,是理解快排、合併排序等進階演算法的基石。