ソートアルゴリズム - マージソート [コード付き]

#マージソートとは何ですか?

簡単に言えば、マージソートは 2 つの順序付けされたシーケンスを統合することです。

推奨チュートリアル: PHP ビデオ チュートリアル

2 つの順序付けされたシーケンスを結合する方法それらを統合しますか？

次に、M = {m1, m2, m3, ...., mx} シーケンスと N = {n1, n2, n3, .... があると仮定します。 , ny} シーケンスの場合、これら 2 つのシーケンスはすでに順序付けされたシーケンスです。最初に空のシーケンス K = {} を作成し、次に m1 と n1 を比較し、m1

マージソートは順序のある配列を統合するものなので、順序のない配列はソートできないということではないでしょうか?この条件は厳しすぎますよね?

マージ ソートは分割統治法に基づいており、完全に無秩序なシーケンスをワイヤレスで分割して、順序付けられたシーケンスを実現できます。例: 今、M={m1 があります。 , m2, m3, ...., mx} の場合、M シーケンスは完全に無秩序なシーケンスです。この場合、M シーケンスはいくつかの小さなシーケンス - {m1, m2}、{m3, m4 ｝....{ mx-1, mx}; 現時点では、これらのシーケンスは順番に並んでおり、マージ操作を通じてソートできるため、マージ ソートは順序のないシーケンスもソートでき、その速度は Stable に属するクイック ソートに次いで 2 番目です。並べ替え。

#シーケンスを分割するにはどうすればよいですか?

前の質問について言及しました。マージ ソートは分割統治に基づいています。分割統治の具体例はパーティション シーケンスに反映されています。例: 今、 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 つずつ実行します。

このアルゴリズムの具体的な手順:

1. 最初のポインター left と middle を指定します (left はシーケンス 1 の最初の要素を指します)。 、右はシーケンス 2 を指します。最初の要素)

2. 左と中央のサイズを比較し、新しく作成されたスペースに小さな要素を配置します。

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 つに分割されます。分離できなくなるまで半分にします。

@2: l はシーケンス 1 の最初の要素を表し、m はシーケンス 2 の最初の要素を表し、k は新しい配列内の既存の要素の数を表します Arr

@3: 最初のシーケンス 1 の要素とシーケンス 2 の最初の要素を比較し、小さい方を Arr に入れ、いずれかのシーケンスの要素が比較されるまでシーケンス カーソルを戻します。

@4: 間の比較プロセスシーケンス 1 とシーケンス 2 の場合、シーケンス 1 はすべて Arr に追加されているように見えますが、シーケンス 2 はまだ追加されていない場合、残りの比較されていない要素は Arr に直接コピーされます

概要:

上記のコードは、本当の意味で配列を分割しません。論理的に分割するだけです。他のコードのように、分割された配列を新しい配列に埋めることはありません。これを行うと、速度とメモリにわずかな影響があります。最小限ではありますが、結局のところそれほど良いものではありません。マージ操作では、パラメーターが境界を越えないように注意する必要があります (なぜ @2 の上の m が mid 1 に等しくなければならないのか、長い間考えていました)実際、その理由は非常に単純で、Mid は左の列に属し、mid 1 から始まる右の列にのみ属するからです。コードも変更する必要がありますが、これ以上無駄な比較を行う必要はありません。私は当時、この問題について真剣に考えました（長い間考えた後...）、実際には、論理的な関係がある限り、明確にすると、コードを簡単に把握できます。

以上がソートアルゴリズム - マージソート [コード付き]の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。