您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> C# >> 關於C#

構建可反轉排序的泛型字典類（二）：排序方向的實現與二分查找優化

編輯：關於C#

核心需求：雙向有序存儲

在設計 ReversibleSortedList<TKey, TValue> 時，核心要求是元素按鍵 TKey 有序存儲，並支援升序（由小到大）與降序（由大到小）兩種模式。最理想的策略是在插入時直接定位正確位置，使集合始終保持有序狀態。在有序陣列中尋找插入點的演算法雖不複雜，但 .NET Framework Class Library (FCL) 已提供高效實現——靜態方法 Array.BinarySearch，採用二分查找（Binary Search），效能最優。

Array.BinarySearch 深度解析

Array.BinarySearch 擁有 8 個重載版本，我們需要的是功能最完整的泛型版本：

public static int BinarySearch<T>(
    T[] array,      // 待搜尋的一維已排序陣列（從零開始）
    int index,      // 搜尋範圍的起始索引
    int length,     // 搜尋範圍的長度
    T value,        // 待搜尋的物件
    IComparer<T> comparer // 比較元素時使用的 IComparer 實作
)

回傳值語義（關鍵在於負數的編碼含義）：

≥ 0：找到 value，回傳其索引。對於不允許重複鍵的字典，此時插入失敗。
< 0：未找到 value。此負數經過位元補運算（bitwise complement，即 ~index）後，編碼了「第一個大於 value 的元素索引」或「最後一個元素索引 + 1」。

這意味著：若回傳值為負數，對其執行 ~returnValue 即可得到確切的插入位置。FCL 這項設計極為周到，讓我們無需額外邏輯即可獲得插入點。

實作 IComparer<T>：排序方向的控制核心

要讓 BinarySearch 支援升/降序切換，需提供實作 IComparer<T> 的比較器。最佳做法是在 ReversibleSortedList 內部宣告巢狀類別 SortDirectionComparer<T>。其核心邏輯在 Compare 方法：根據 ListSortDirection 列舉（Ascending/Descending）決定是否反轉比較結果。

關鍵程式碼片段

public class SortDirectionComparer<T> : IComparer<T>
{
    private ListSortDirection _sortDir = ListSortDirection.Ascending;

    public SortDirectionComparer() { }
    public SortDirectionComparer(ListSortDirection sortDir) 
    { 
        _sortDir = sortDir; 
    }

    public ListSortDirection SortDirection
    {
        get { return _sortDir; }
        set { _sortDir = value; }
    }

    public int Compare(T lhs, T rhs)
    {
        // 注意：此處為示範簡化，實際專案建議用 Comparer<T>.Default
        int compareResult = lhs.ToString().CompareTo(rhs.ToString());
        if (_sortDir == ListSortDirection.Descending)
            compareResult *= -1;
        return compareResult;
    }
}

ReversibleSortedList 0.2 版本完整架構

在 0.1 版本（雛形）基礎上，新增 SortDirectionComparer 並整合靜態建構子最佳化陣列初始化：

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;

public class ReversibleSortedList<TKey, TValue>
{
    #region 成員變數
    private TKey[] keys = new TKey[0];
    private TValue[] values = new TValue[0];
    private static TKey[] emptyKeys;
    private static TValue[] emptyValues;
    #endregion

    #region 建構子
    static ReversibleSortedList()
    {
        emptyKeys = new TKey[0];
        emptyValues = new TValue[0];
    }

    public ReversibleSortedList()
    {
        this.keys = emptyKeys;
        this.values = emptyValues;
    }
    #endregion

    #region 公用屬性
    public int Capacity => this.keys.Length;
    #endregion

    #region 排序方向比較器（巢狀類別）
    public class SortDirectionComparer<T> : IComparer<T>
    {
        private ListSortDirection _sortDir = ListSortDirection.Ascending;

        public SortDirectionComparer() { }
        public SortDirectionComparer(ListSortDirection sortDir) 
        { 
            _sortDir = sortDir; 
        }

        public ListSortDirection SortDirection
        {
            get { return _sortDir; }
            set { _sortDir = value; }
        }

        public int Compare(T lhs, T rhs)
        {
            int result = Comparer<T>.Default.Compare(lhs, rhs);
            return _sortDir == ListSortDirection.Descending ? -result : result;
        }
    }
    #endregion
}

public class Test
{
    static void Main()
    {
        var rs = new ReversibleSortedList<int, string>();
        Console.WriteLine(rs.Capacity); // 輸出 0
    }
}

設計亮點總結

零分配初始化：透過 static 建構子共享 emptyKeys/emptyValues，避免每個實例建立長度為 0 的陣列，減少 GC 壓力。
二分查找複用：直接使用 Array.BinarySearch，獲得 O(log n) 查找與插入點定位，且自帶「未找到時回傳插入位置編碼」特性。
策略模式分離排序邏輯：SortDirectionComparer 封裝升/降序切換，符合開放封閉原則，後續擴充自定義比較器極為容易。

下一步將實作 Add、Remove 等核心方法，並處理陣列擴容與鍵值同步移動邏輯。