什么是归并排序?
归并排序简单来讲, 就是将两个有序的序列整合到一起.
如何将两个有序的序列整合到一起呢?
那么我们假设, 现在有 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];
- }
- }
- }
- View Code
代码解读:
@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 不是不行, 只是后面的代码也需要改, 但是没有必要多做一次无用比较, 这个问题我当时真是想了半天...), 其实只要理清楚其中的逻辑关系, 这样代码就能做到信手拈来.
来源: https://www.cnblogs.com/CHANGKTITI/p/11395289.html