算法-归并排序

归并排序，英文名称是MERGE-SORT。它是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

比较 a[i] 和 b[j] 的大小，若 a[i]≤b[j]，则将第一个有序表中的元素 a[i] 复制到 r[k] 中，并令 i 和 k 分别加上1；否则将第二个有序表中的元素b[j]复制到 r[k] 中，并令 j 和 k 分别加上1；如此循环下去，直到其中一个有序表取完；然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。

归并排序评价

归并排序的最坏时间复杂度为O(nlogn) ，是一种稳定排序算法

代码实现

#region 归并排序
        /// <summary>
        /// 合并
        /// </summary>
        /// <param name="arr">合并的数组</param>
        /// <param name="L">最左边的下标</param>
        /// <param name="M">左右两个数组的中间段</param>
        /// <param name="R">最右的下标</param>
        static void merge( int [] arr,int L,int M,int R)
        {
            int Left_Size =M-L+1 ;
            int Right_Size =R-M ;
            int [] Left=new int[Left_Size];
            int[] Right = new int[Right_Size];
            int i,j,k;
            for (i = L; i <= M; i++)
            {
                Left[i - L] = arr[i];
            }
            for (i = M+1; i <R; i++)
            {
                Right[i - M] = arr[i];
            }
            i = 0; j = 0; k = L;
            while (i<Left_Size && j<Right_Size)
            {
                if (Left[i] < Right[j])
                {
                    arr[k] = Left[i];
                    i++;
                    k++;
                }
                else
                {
                    arr[k] = Right[j];
                    j++;
                    k++;
                }
            }
            while (i<Left_Size)
            {
                arr[k] = Left[i];
                i++;
                k++;
            }
            while (j<Right_Size)
            {
                arr[k] = Right[j];
                j++;
                k++;
            }
        }