排序算法—归并排序【附代码】
排序算法—归并排序【附代码】
内容导读
收集整理的这篇技术教程文章主要介绍了排序算法—归并排序【附代码】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3672字，纯文字阅读大概需要6分钟。
内容图文
什么是归并排序？
归并排序简单来讲，就是将两个有序的序列整合到一起。
推荐教程：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 不是不行，只是后面的代码也需要改，但是没有必要多做一次无用比较，这个问题我当时真是想了半天...），其实只要理清楚其中的逻辑关系，这样代码就能做到信手拈来。
以上就是排序算法—归并排序【附代码】的详细内容，更多请关注Gxl网其它相关文章！
内容总结
以上是为您收集整理的排序算法—归并排序【附代码】全部内容，希望文章能够帮你解决排序算法—归并排序【附代码】所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
