本文共 1760 字，大约阅读时间需要 5 分钟。

十大常用的排序算法之归并排序 C#实现

算法描述

  什么是归并排序呢？归并排序，英文名“Merge Sort”。算法的主要思想为四个字——“分而治之”。将一个无序数组拆分成若干的子序列，然后归并子序列时，对其进行排序，这样可以得到若干个有序的子序列。将已有序的子序列合并，得到完全有序的序列。

举个栗子：

现在有这样一个序列：{6，5，3，1，8，7，2，4} 我们将其拆分为两个子序列：{6，5，3，1}，{8，7，2，4} 子序列可以继续拆分成四个子序列：{6，5}，{3，1}，{8，7}，{2，4} 继续拆分八个子序列：{6}，{5}，{3}，{1}，{8}，{7}，{2}，{4} 这时候发现子序列不可以继续拆分下去了，ok，开始合并。合并的规则是每两个子序列合并，合并时，将序列中的元素，升序排序。

排序过程如下图所示：

算法实现 C#

//归并排序        public static int[] MergeSort(int[] arr,int left ,int right, int[] tempArr)        {
               //当left小于right时说明还可以继续拆分下去            if (left < right)            {
                   int center = (left + right) / 2;                MergeSort(arr, left, center,tempArr);                MergeSort(arr, center + 1, right,tempArr);                Meger(arr, left, center, right,tempArr);            }            return arr;        }        //合并子序列        public static void Meger(int[] arr, int left,int center,int right,int[] tempArr)        {
               //定义两个子序列起始下标 i j            int i = left, j = center+1;            for (int k = left; k <= right; k++)            {
                   if (i > center)                {
                       tempArr[k] = arr[j++];                }                else if (j > right)                {
                       tempArr[k] = arr[i++];                }                else if (arr[i] <= arr[j])                 {
                       tempArr[k] = arr[i++];                }                else                {
                       tempArr[k] = arr[j++];                }            }            //将有序的子序列 合并到元素组中            for (int k = left; k <= right; k++)            {
                   arr[k] = tempArr[k];            }        }

算法分析

  归并排序是稳定排序()，平均时间复杂度为O(nlogn)，空间复杂度O(n)（需要一个长度和原数组相等的临时数组来排序，所以是O(n)）。

转载地址：https://blog.csdn.net/m0_56500170/article/details/115358452 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！