排序详解之归并排序

本文章将介绍归并排序，时间复杂度为n*lg(n)的归并排序，不仅效率高，而且是稳定的（而堆排序，快排是不稳定的）。

要排序的数组：

5 , 1, 9 ,3, 7 , 4 , 8 ,6 , 2

归并排序过程：

1.      计算组元素个数,count ,以count=2为起始个数，每次count*=2,count∈[2,arr.Count]

2.      每次把数组元素以count为一组，进行分组，对每一组进行排序

3.      把排序好的组与相邻的组进行归并，合并为同一组，同时count*=2

4.      不断分组，增加count个数，直到count为arr.Count（即数组长度）为止

现在我们过一遍这个流程。

至于归并两个组的过程，就不详细讨论了，可以选择插入排序，把第二个组的数组插入到第一个组。

参考代码：

public List<int>MergeSort(List<int> arr)
        {
            List<int> lastOne = null;
            if (arr.Count % 2 != 0)
            {
                lastOne = new List<int> {arr[arr.Count - 1] };
                arr.RemoveAt(arr.Count - 1);
            }
 
            var groups = newQueue<List<int>>();
            foreach (var a in arr)
            {
                groups.Enqueue(newList<int> { a });
            }
 
            if (lastOne == null)
            {
                while (groups.Count > 1)
                {
                    var ret =Merge2Arr(groups.Dequeue(), groups.Dequeue());
                    groups.Enqueue(ret);
                }
                return groups.Dequeue();
            }
 
            while (groups.Count > 1)
            {
                var ret =Merge2Arr(groups.Dequeue(), groups.Dequeue());
                groups.Enqueue(ret);
            }
            return Merge2Arr(groups.Dequeue(),lastOne);
        }
 
        private List<int>Merge2Arr(List<int> arr1, List<int> arr2)
        {
            var ret = new List<int>();
            if (arr1.Count == 1)
            {
                if (arr1[0] > arr2[0])
                {
                    ret.Add(arr2[0]);
                    ret.Add(arr1[0]);
                }
                else
                {
                    ret.Add(arr1[0]);
                    ret.Add(arr2[0]);
                }
                return ret;
            }
 
            if (arr1[0] > arr2[0])
            {
                arr2.ForEach(ret.Add);
               
                for (int j = 0; j <arr1.Count; j++)
                {
                    var isInserted = false;
                    for (int i = 0; i <ret.Count - 1; i++)
                    {
                        if (ret[i] < arr1[j]&& ret[i + 1] >= arr1[j])
                        {
                            ret.Insert(i+1, arr1[j]);
                            isInserted = true;
                            break;
                        }
                    }
                    if (!isInserted)
                    {
                        if(arr1[j] <ret[ret.Count - 1]) ret.Insert(0,arr1[j]);
                        else   ret.Add(arr1[j]);
                       
                    }
                     
                }
            }
            else
            {
                arr1.ForEach(ret.Add);
                for (int j = 0; j <arr2.Count; j++)
                {
                    var isInserted = false;
                    for (int i = 0; i <ret.Count - 1; i++)
                    {
                        if (ret[i] < arr2[j] && ret[i +1] >= arr2[j])
                        {
                            ret.Insert(i+1,arr2[j]);
                            isInserted = true;
                            break;
                        }
                    }
                    if (!isInserted)
                    {
                        if (arr2[j] <ret[ret.Count - 1]) ret.Insert(0, arr2[j]);
                        else ret.Add(arr2[j]);
                    }
                }
            }
            return ret;
        }

相信你现在已经明白了归并排序。

感谢您的阅读！