演算法實例-C#-歸併排序-MergeSort

# 演算法實例 #

排序演算法Sort

歸併排序MergeSort

演算法說明

1. 歸併的思路是任意兩個元素可以比較大小,那麼任意兩個有序的元素集合也可以通過比較大小的方式歸併成一個有序的元素集合
2. 任何的無序元素集合可以拆分的最小的可比較單位是元素本身,例如List list = new List() { 23, 42, 4, 16, 8, 23, 15, 3, 9, 55, 0, 23, 34, 12, 2, 46, 25, 25 };可以拆分到最小的元素為{{23},{42},{4},{16},{8},{23},{15},{3},{9},{55},{0},{23},{34},{12},{2},{46},{25},{25}},如果我們將這些元素組合兩兩比較就可以得到新的一組有序的元素組合{{23,24},{4,16},{8,23},{3,15},{9,55},{0,23},{12,34},{2,46},{25,25}}
3. 對於上訴的元素集合進行比較後的有序元素集合,如下圖

最基本元素(即不可拆分最小元素集合)

第一次兩兩歸併

第二次兩兩歸併

第三次兩兩歸併

第四次兩兩歸併

最終合一的歸併

演算法步驟

1.我的演算法中使用隊列來作為容器容納元素,最小可比較單位也就是隊列中只有壹個元素,同時在外層也使用隊列來分別容納歸併的隊列即使用 Queue<Queue<T>> 的結構,其中 Queue<Queue<T>>是壹個歸併隊列的集合(如[{23,24},{4,16}]),Queue<T>是有序元素的集合(如{23,24})
2.遞歸的跳出條件是,歸併完成即Queue<Queue<T>>的元素個數Count為壹.且每一次遞歸完成一次兩兩歸併.
3.使用隊列的好處在於,可以使用Peek()和Dequeue()方法來確定參與一次歸併的隊列Queue<T> _tempLeft和Queue<T> _tempRight哪一個先出對歸並到新的有序集合中.

代碼示例

public static class MergeSorterA
{

    /// <summary>
    /// Public merge-sort API
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="collection"></param>
    /// <param name="comparer"></param>
    public static void MergeSortA<T>(this Queue<T> collection, Comparer<T> comparer = null)
    {
        comparer = comparer ?? Comparer<T>.Default;
        Queue<Queue<T>> _queue = new Queue<Queue<T>>();
        while (collection.Count !=0 )
        {
            Queue<T> _temp = new Queue<T>();
            _temp.Enqueue(collection.Dequeue());
            _queue.Enqueue(_temp);
        }

        _queue.InternalMergeSortA(comparer);

        foreach (var item in _queue.Dequeue())
        {
            collection.Enqueue(item);
        }
    }
    

    /// <summary>
    /// Implements the recursive merge-sort algorithm
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="collectionQueue"></param>
    /// <param name="comparer"></param>
    private static void InternalMergeSortA<T>(this Queue<Queue<T>> collectionQueue, Comparer<T> comparer)
    {
        Queue<Queue<T>> _listQueue = new Queue<Queue<T>>();
        
        while (collectionQueue.Count != 0)
        {
            Queue<T> _queue = new Queue<T>();
            Queue<T> _tempLeft = new Queue<T>();
            Queue<T> _tempRight = new Queue<T>();
            _tempLeft = collectionQueue.Dequeue();
            //make sure _tmepLeft is not the ends
            if (collectionQueue.Count != 0)
            {
                _tempRight = collectionQueue.Dequeue();
            }
            int _length = _tempLeft.Count + _tempRight.Count;
            for (int i = 0; i < _length; i++)
            {
                if (_tempLeft.Count > 0 && _tempRight.Count > 0)
                {
                    _queue.Enqueue(comparer.Compare(_tempLeft.Peek(), _tempRight.Peek()) <= 0 ? _tempLeft.Dequeue() : _tempRight.Dequeue());
                }
                else if (_tempLeft.Count > 0)
                {
                    _queue.Enqueue(_tempLeft.Dequeue());
                }
                else if (_tempRight.Count > 0)
                {
                    _queue.Enqueue(_tempRight.Dequeue());
                }
            }
            _listQueue.Enqueue(_queue);
        }


        if (_listQueue.Count > 1)
        {
            _listQueue.InternalMergeSortA(comparer);
        }
        collectionQueue.Clear();
       
        foreach (var item in _listQueue)
        {
            collectionQueue.Enqueue(item);
        }
    }

}

測試用例

[TestMethod]
    public void TestMethod3()
    {
        List<int> list = new List<int>() { 23, 42, 4, 16, 8, 23, 15, 3, 9, 55, 0, 23, 34, 12, 2, 46, 25, 25 };
        Queue<int> _queue = new Queue<int>(list);
        _queue.MergeSortA();
        Assert.Fail();
    }