C#のマージソート

C# マージソート

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
namespace Sort  
{  
    class MergeSorter  
    {  
        /// <summary>  
        /// 归并排序之归：归并排序入口   
        /// </summary>  
        /// <param name="data">无序数组</param>  
        /// <returns>有序数组</returns>  
         public static int[] Sort(int[] data)  
        {  
            //若data为null，或只剩下1 or 0个元素，返回，不排序  
            if (null == data || data.Length <= 1)  
            {  
                return data;  
            }  
            //取数组中间下标  
            int middle = data.Length >> 1;  
            //初始化临时数组let,right，并定义result作为最终有序数组，若数组元素奇数个，将把多余的那元素空间预留在right临时数组  
            int[] left = new int[middle];  
            int[] right =  new int[data.Length - middle];  
            int[] result = new int[data.Length];  
            for (int i = 0; i < data.Length; i++)  
            {  
                if (i < middle)  
                {  
                    left[i] = data[i];  
                }  
                else  
                {  
                    right[i-middle] = data[i]; //此处i-middle，让我省掉定义一个j，性能有所提高  
                }  
            }  
            left = Sort(left);//递归左数组  
            right = Sort(right);//递归右数组  
            result = Merge(left, right);//开始排序  
            return result;  
        }  
        /// <summary>  
        /// 归并排序之并:排序在这一步  
        /// </summary>  
        /// <param name="a">左数组</param>  
        /// <param name="b">右数组</param>  
        /// <returns>合并左右数组排序后返回</returns>  
         private static int[] Merge(int[] a, int[] b)  
         {  
            //定义结果数组，用来存储最终结果  
            int[] result = new int[a.Length + b.Length];  
            int i = 0, j = 0, k = 0;  
            while (i < a.Length && j < b.Length)  
            {  
                if (a[i] < b[j])//左数组中元素小于右数组中元素  
                {  
                    result[k++] = a[i++];//将小的那个放到结果数组  
                }  
                else//左数组中元素大于右数组中元素  
                {  
                    result[k++] = b[j++];//将小的那个放到结果数组  
                }  
            }  
            while (i < a.Length)//这里其实是还有左元素，但没有右元素   
            {  
                result[k++] = a[i++];  
            }  
            while (j < b.Length)//有右元素，无左元素  
            {  
                result[k++] = b[j++];  
            }  
            return result;//返回结果数组  
        }  
    }  
}

マージソート:
マージソート方法は、2 つ (またはそれ以上) の順序付きリストを新しい順序付きリストにマージすることです。つまり、ソートされるシーケンスをいくつかのサブシーケンスに分割します。次に、順序付けられたサブシーケンスを順序付けられたシーケンス全体にマージします。このアルゴリズムは、分割統治法 (Divide and Conquer) を使用する非常に典型的なアプリケーションです。

順序付けされたサブシーケンスをマージして、完全に順序付けされたシーケンスを取得します。つまり、最初に各サブシーケンスを順序付けてから、サブシーケンス セグメントを順序付けします。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それは双方向マージと呼ばれます。

ソートされていないシーケンスがあると仮定します。まず、分割メソッドを使用してシーケンスをソート済みのサブシーケンスに分割し、次にマージメソッドを使用してサブシーケンスをマージして、ソート済みの良好なシーケンスを作成します。セグメント化とマージのプロセスは、以下の凡例で見ることができます。

上の図からわかるように、まず未分類のシーケンスを真ん中から2つの部分に分割し、次にその2つの部分を4つの部分に分割し、さらにそれが分割されるまで順番に分割します。次に、これらのデータをペアとしてマージし、マージを続けて、最終的に順序付けられたシーケンスになります。

2 つのソートされたサブシーケンスを 1 つのソートされたシーケンスにマージするにはどうすればよいですか?以下の方法を参照してください。

2 つのソートされたサブシーケンスがあると仮定します。

シーケンス A: 1 23 34 65

シーケンス B: 2 13 14 87

次に、以下の手順に従って、それらを 1 つのシーケンスにマージします。

(1) まず新しいシーケンス C[8] を設定します。
(2) A[0] と B[0] を比較、A[0] = 1、B[0] = 2、A[0] (3) ) A[1] と B[0] を比較すると、A[1] = 23、B[0] = 2、A[1] > B[0]、C[1] = 2
(4) A[ 1] と B[1] を比較すると、A[1] = 23、B[1] = 13、A[1] > B[1]、その後 C[2] = 13
(5) A[1] B[2]、A[1] = 23、B[2] = 14、A[1] > B[2]、その後 C[3] = 14
(6) A[1] と B[3] ] 比較、A[1] = 23、B[3] = 87、A[1] (7) A[2] と B[3] を比較、 A[2] = 34、B[3] = 87、A[2] (8) A[3] と B[3] を比較すると、A[3] ] = 65、B[3] = 87、A[3] (9) 最後に、B[3] を C にコピーし、その後 C[7] = 87 。マージが完了しました。

C#のシフト演算(左シフトと右シフト)

マージソート、時間計算量はO(nlogn)です。

マージソートの効率は比較的高く、配列の長さを N とすると、配列を 10 進数の系列に分割するのに logN ステップかかり、時間計算量は O として記録されます。 (N) なので、合計は O(N*logN) になります。マージ ソートは毎回隣接するデータに対して実行されるため、O(N*logN) でのマージ ソートのいくつかのソート方法 (クイック ソート、ヒル ソート、ヒープ ソート) も比較的効率的です。

上記は C# マージソートの内容です。さらに関連する内容については、PHP 中国語 Web サイト (www.php.cn) をご覧ください。