萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

C# 資料結構實戰:冒泡排序演算法完整解析

演算法核心思想

冒泡排序透過相鄰元素兩兩比較、交換,將最大(或最小)元素逐輪「冒泡」至陣列末端。雖時間複雜度為 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)原地排序,僅需常數額外空間
穩定性穩定相等元素不交換,相對順序不變

教學重點總結

  1. 雙層迴圈邊界:外層 pass < n-1,內層 i < n-1-pass 避免重複比較已排序區
  2. 提前結束優化:引入 swapped 標記,最佳情況降為 O(n)
  3. 原地交換:使用 Swap 輔助方法提升可讀性
  4. 泛型化延伸:實務上可改寫為 void BubbleSort(T[] arr) where T : IComparable<T> 支援任意可比較型別

冒泡排序雖非生產環境首選,但掌握其邊界控制與優化技巧,是理解快排、合併排序等進階演算法的基石。

copyright © 萬盛學電腦網 all rights reserved