排序算法—归并排序【附代码】

作者 : shijian 本文共2251个字,预计阅读时间需要6分钟 发布时间: 2019-10-21 共42人阅读

什么是归并排序?

  归并排序简单来讲,就是将两个有序的序列整合到一起。

推荐教程:PHP视频教程

如何将两个有序的序列整合到一起呢?

  那么我们假设,现在有 M={m1 ,m2,m3,….,mx}序列和 N = {n1,n2,n3,….,ny}序列,这两个序列已经是有序的序列,首先创建一个空序列 K = {},那么接着将 m1 和 n1 进行比较,加入 m1 < n1 那么将 m1 放入 K 序列中,然后 M 序列游标后移,即下一次将进行 m2 和 n1 的比较,直到全部比较完毕,并填入序列 K 中。

既然归并排序是整合有序序列,那么岂不是不能排序无序序列,这条件也太苛刻了点吧?

  归并排序是建立在分治法的基础上进行操作的,也就是可以将一个完全无序的序列进行无线分割以达到有序序列,比如:现在有 M={m1 ,m2,m3,….,mx},M序列是完全无序的序列,那么此时可以将 M 序列分成若干个小序列——{m1,m2},{m3,m4}….{mx-1,mx};此时这些序列就是有序的,那么就可以通过归并操作进行排序,所以归并排序也可以排序无序序列,且速度仅次于快速排序,属于稳定排序。

如何分割序列?

  上个问题已经提过,归并排序是建立在分治的基础上进行操作的,其中分治的体现就体现在分割序列上,比如:现在有M={m1 ,m2,m3,….,mx},第一次分割:M1 = {m1,m2,…,m(x+1)/2},M2 = {m(x+1)/2 +1,m(x+1)/2 +2,…,mx},第一次分割之后得到 M1 和 M2 序列,然后再分割 M1 和 M2 ,分割若干次之后得到 x/2 + x%2 个序列,然后再逐一进行归并操作。

该算法具体步骤:

  1、规定首指针 left 和mid(left指向序列1的首元素,right 指向序列2的首元素)

  2、比较 left 和 mid 的大小,将小的元素放入新建的空间中

  3、重复步骤2,直到其中一个序列遍历完毕

  4、将剩下的未加入新建空间中的元素直接复制粘贴进新建空间

该算法的核心步骤:

  1、使用分治法(递归)分割序列

  2、比较 left 和 mid 的大小 , 将小的元素的添加进入新建空间

讲述完毕,贴上代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 排序__归并排序
{
    class 归并
    {

        public static int[] arr = { 6, 202, 301, 100, 38, 8, 1 ,-1,1000};
        static void Main(string[] args)
        {
            Sort(arr, 0, arr.Length -1);
            foreach (var item in arr)
            {
                Console.Write(item + "  ");
            }
            Console.ReadKey();
        }

        public static void Sort(int []a,int left,int right)
        {
            if (left >= right) return;
            else
            {
                int mid = (left + right) / 2;                //@1
                Sort(a, left, mid);
                Sort(a, mid + 1, right);
                MergeSort(a, left, mid, right);
            }
        }

        public static void MergeSort(int []a,int left,int mid,int right)
        {
            int[] Arr = new int[right - left + 1];
            int l = left, m = mid +1 , k = 0;           //@2
            while ( m <= right && l <= mid )          //@3
            {
                if (a[l] > a[m]) Arr[k++] = a[m++];
                else Arr[k++] = a[l++];
            }
            while (m < right +1)                           //@4
            {
                Arr[k++] = a[m++];
            }
            while (l < mid +1 )  Arr[k++] = a[l++];        //@4
            for (k = 0, l = left; l < right + 1; k++, l++) a[l] = Arr[k];
        }
    }
}

代码解读:

  @1 :Sort()函数完成了序列的分割,每一次递归都将序列分成两半,直到不能分隔为止。

  @2 :l 代表序列1的首元素,m 代表序列2的首元素,k代表新建数组Arr的已有元素个数

  @3 :序列1的首元素和序列2的首元素进行比较,将小的放入 Arr 中,且序列游标后移,直到其中一个序列的元素遍比较完毕

  @4 :在序列1 和序列2的比较过程中,可能出现序列1已经全部添加进了 Arr 中,但是序列2还没有,则将剩下的未比较的元素直接复制进入 Arr 中

总结:

  以上代码并不是真正意义上的分割数组,只是做了一个逻辑分割,没有像其他代码一样将分割后的数组填入一个新的数组,那样做的话会对速度和内存产生一点影响,虽然微乎其微,但是总归是没这么好的,在归并操作上,需要注意的是参数不要越界(我当时就想了很久为什么 @2 上面的 m 要等于 mid +1 而不是 mid ,其实道理很简单,因为mid是属于左序列,从 mid+1 开始才属于右序列,将m = mid +1 改成 m = mid 不是不行,只是后面的代码也需要改,但是没有必要多做一次无用比较,这个问题我当时真是想了半天…),其实只要理清楚其中的逻辑关系,这样代码就能做到信手拈来。

以上就是排序算法—归并排序【附代码】的详细内容,更多请关注吆喝资源网其它相关文章!

本文转自PHP中文网,吆喝网(http://yaoohe.com)搜集整理,如有疑问请联系本站客服!

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"yaoohe.com",如遇到无法解压的请联系管理员!
吆喝资源网 » 排序算法—归并排序【附代码】

常见问题FAQ

提示下载完但解压或打开不了?
最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。 若排除这种情况,可在对应资源底部留言,或 联络我们。

发表评论