排序算法—归并排序【附代码】-php教程

甚么是归并排序？

　　归并排序简略来说，就是将两个有序的序列整合到一同。

保举教程：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 个序列，而后再逐一进行归并操作。

该算法详细步骤：

　　一、规则首指针 left 以及mid（left指向序列1的首元素，right 指向序列2的首元素）

　　二、比拟 left 以及 mid 的巨细，将小的元素放入新建的空间中

　　三、反复步骤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 没有是没有行，只是前面的代码也需求改，然而不须要多做一次无用比拟，这个成绩我过后真是想了半天...），其实只需理分明此中的逻辑关系，这样代码就能做到信手拈来。

以上就是排序算法—归并排序【附代码】的具体内容，更多请存眷资源魔其它相干文章！