php排序算法—?dú)w并排序的案例

這篇文章將為大家詳細(xì)講解有關(guān)php排序算法—?dú)w并排序的案例，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

什么是歸并排序？

　　歸并排序簡(jiǎn)單來(lái)講，就是將兩個(gè)有序的序列整合到一起。

如何將兩個(gè)有序的序列整合到一起呢？

　　那么我們假設(shè)，現(xiàn)在有 M=｛m1 ，m2，m3，....，mx｝序列和 N = ｛n1，n2，n3，....，ny｝序列，這兩個(gè)序列已經(jīng)是有序的序列，首先創(chuàng)建一個(gè)空序列 K = ｛｝，那么接著將 m1 和 n1 進(jìn)行比較，加入 m1 < n1 那么將 m1 放入 K 序列中，然后 M 序列游標(biāo)后移，即下一次將進(jìn)行 m2 和 n1 的比較，直到全部比較完畢，并填入序列 K 中。

既然歸并排序是整合有序序列，那么豈不是不能排序無(wú)序序列，這條件也太苛刻了點(diǎn)吧？

　　歸并排序是建立在分治法的基礎(chǔ)上進(jìn)行操作的，也就是可以將一個(gè)完全無(wú)序的序列進(jìn)行無(wú)線分割以達(dá)到有序序列，比如：現(xiàn)在有 M=｛m1 ，m2，m3，....，mx｝，M序列是完全無(wú)序的序列，那么此時(shí)可以將 M 序列分成若干個(gè)小序列——｛m1，m2｝，｛m3，m4｝....｛mx-1，mx｝；此時(shí)這些序列就是有序的，那么就可以通過(guò)歸并操作進(jìn)行排序，所以歸并排序也可以排序無(wú)序序列，且速度僅次于快速排序，屬于穩(wěn)定排序。

如何分割序列？

　　上個(gè)問(wèn)題已經(jīng)提過(guò)，歸并排序是建立在分治的基礎(chǔ)上進(jìn)行操作的，其中分治的體現(xiàn)就體現(xiàn)在分割序列上，比如：現(xiàn)在有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 個(gè)序列，然后再逐一進(jìn)行歸并操作。

該算法具體步驟：

　　1、規(guī)定首指針 left 和mid（left指向序列1的首元素，right 指向序列2的首元素）

　　2、比較 left 和 mid 的大小，將小的元素放入新建的空間中

　　3、重復(fù)步驟2，直到其中一個(gè)序列遍歷完畢

　　4、將剩下的未加入新建空間中的元素直接復(fù)制粘貼進(jìn)新建空間

該算法的核心步驟：

　　1、使用分治法（遞歸）分割序列

　　2、比較 left 和 mid 的大小 ， 將小的元素的添加進(jìn)入新建空間

講述完畢，貼上代碼：

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（）函數(shù)完成了序列的分割，每一次遞歸都將序列分成兩半，直到不能分隔為止。

　　@2 ：l 代表序列1的首元素，m 代表序列2的首元素，k代表新建數(shù)組Arr的已有元素個(gè)數(shù)

　　@3 ：序列1的首元素和序列2的首元素進(jìn)行比較，將小的放入 Arr 中，且序列游標(biāo)后移，直到其中一個(gè)序列的元素遍比較完畢

　　@4 ：在序列1 和序列2的比較過(guò)程中，可能出現(xiàn)序列1已經(jīng)全部添加進(jìn)了 Arr 中，但是序列2還沒(méi)有，則將剩下的未比較的元素直接復(fù)制進(jìn)入 Arr 中

總結(jié)：

　　以上代碼并不是真正意義上的分割數(shù)組，只是做了一個(gè)邏輯分割，沒(méi)有像其他代碼一樣將分割后的數(shù)組填入一個(gè)新的數(shù)組，那樣做的話會(huì)對(duì)速度和內(nèi)存產(chǎn)生一點(diǎn)影響，雖然微乎其微，但是總歸是沒(méi)這么好的，在歸并操作上，需要注意的是參數(shù)不要越界（我當(dāng)時(shí)就想了很久為什么 @2 上面的 m 要等于 mid +1 而不是 mid ，其實(shí)道理很簡(jiǎn)單，因?yàn)閙id是屬于左序列，從 mid+1 開(kāi)始才屬于右序列，將m = mid +1  改成 m = mid 不是不行，只是后面的代碼也需要改，但是沒(méi)有必要多做一次無(wú)用比較，這個(gè)問(wèn)題我當(dāng)時(shí)真是想了半天...），其實(shí)只要理清楚其中的邏輯關(guān)系，這樣代碼就能做到信手拈來(lái)。

關(guān)于php排序算法—?dú)w并排序的案例就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。