Net Core教程

【C# 排序】归并排序 merge sort

本文主要是介绍【C# 排序】归并排序 merge sort,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

定义

归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。 若将两个有序表合并成一个有序表,称为二路归并

  O ( n log ⁡ n ) {\displaystyle O(n\log n)} {\displaystyle O(n\log n)}(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。  O ( n log ⁡ n ) {\displaystyle O(n\log n)} {\displaystyle O(n\log n)}(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  • 自下而上的迭代;

算法步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

  4. 重复步骤 3 直到某一指针达到序列尾;

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

     

动图演示

 

空间复杂度

nlogn+n,递归堆栈+数组

时间复杂度

nlogn,归并的过程类型二叉树高度,所以时间复杂度就是树高

 

 

 

稳定性

稳定

C#代码

 

        public static void MergeSort(int[] array1)
        {
            int low = 0, heigh = array1.Length - 1;
            Mergesort(array1, low,  heigh);
        }
           
           private static void  Mergesort(int[] array1,int low,int heigh)
        {
            
  
            if (low < heigh)
            {
               int mid = (low+heigh) / 2;
                Mergesort(array1,low,mid);
                Mergesort(array1, mid + 1, heigh);
                BinaryMerge(array1,low,mid,heigh);
            }
           
        }
        public static void BinaryMerge(int[] array, int low,int mid,int height)
        {
            int[] temparray = new int[array.Length];
            int left, right,index;
            //复制数组
            for (index = low; index <= height; index++)
            {
                temparray[index] = array[index];
            }
          
            //二路归并
            for ( index= left = low,right=mid+1;left<=mid&& right <= height && index <=height; index++)
            {
                if (temparray[left] <= temparray[right]) { array[index] = temparray[left++]; }
                else { array[index] = temparray[right++]; }
            }
            //检查那个部分没拷贝完成,将temparray剩余的部分拷贝到array数组中
            while (left<=mid) array[index++] = temparray[left++];
            while(right<=height) array[index++]=temparray[right++];
        }

 

这篇关于【C# 排序】归并排序 merge sort的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!