Tri par fusion C#

Tri par fusion 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;//返回结果数组  
        }  
    }  
}

Tri par fusion :
La méthode de tri par fusion consiste à fusionner deux (ou plus) listes ordonnées en une nouvelle liste ordonnée, c'est-à-dire diviser la séquence à trier en plusieurs sous-séquences, et chaque sous-séquence est ordonnée. Fusionnez ensuite les sous-séquences ordonnées dans la séquence ordonnée globale. Cet algorithme est une application très typique utilisant la méthode diviser pour régner (Divide and Conquer).

Fusionnez les sous-séquences ordonnées pour obtenir une séquence complètement ordonnée ; c'est-à-dire, triez d'abord chaque sous-séquence, puis triez les segments de sous-séquence. Si deux listes ordonnées sont fusionnées en une seule liste ordonnée, on parle de fusion bidirectionnelle.

Supposons que nous ayons une séquence non triée, nous utilisons d'abord la méthode de fractionnement pour diviser la séquence en sous-séquences triées, puis utilisons la méthode de fusion pour séparer les sous-séquences une par une. Les séquences sont fusionnées en séquences triées. Le processus de segmentation et de fusion est visible dans la légende ci-dessous.

Comme vous pouvez le voir sur l'image ci-dessus, nous divisons d'abord une séquence non triée en 2 parties à partir du milieu, puis divisons la 2 parties en Divisez-le en 4 parties et divisez-le en séquence jusqu'à ce qu'il soit divisé en données une par une, puis fusionnez ces données ensemble pour les rendre ordonnées, continuez à fusionner et enfin devenez une séquence ordonnée.

Comment fusionner deux sous-séquences triées en une seule séquence triée ? Vous pouvez vous référer à la méthode ci-dessous.

Supposons que nous ayons deux sous-séquences triées.

Séquence A : 1 23 34 65

Séquence B : 2 13 14 87

Ensuite, vous pouvez suivre les étapes ci-dessous pour les fusionner en une seule séquence.

(1) Définissez d’abord une nouvelle séquence C[8].
(2) Comparez A[0] et B[0], A[0] = 1, B[0] = 2, A[0] (3) En comparant A[1] et B[0], A[1] = 23, B[0] = 2, A[1] > >(4) En comparant A[1] et B[1], A[1] = 23, B[1] = 13, A[1] > (5) En comparant A[1] et B[2], A[1] = 23, B[2] = 14, A[1] > 6) En comparant A[1] et B[3], A[1] = 23, B[3] = 87, A[1]




Opération de décalage C# (décalage à gauche et décalage à droite)

Tri par fusion, Le la complexité temporelle est O(nlogn).

L'efficacité du tri par fusion est relativement élevée. Supposons que la longueur de la séquence soit N. Il faut logN étapes pour séparer la séquence en séquences décimales. Chaque étape est un processus de fusion de séquences ordonnées. être enregistré comme O(N), donc le total est O(N*logN). Étant donné que le tri par fusion fonctionne à chaque fois sur des données adjacentes, plusieurs méthodes de tri par fusion (tri rapide, tri par fusion, tri Hill, tri par tas) dans O(N*logN) sont également relativement efficaces.

Ce qui précède est le contenu du tri par fusion C#. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !