C#-Zusammenführungssortierung

C# Zusammenführungssortierung

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

Zusammenführungssortierung:
Die Zusammenführungssortierungsmethode besteht darin, zwei (oder mehr) geordnete Listen zu einer neuen geordneten Liste zusammenzuführen, d. h. die zu sortierende Sequenz in mehrere aufzuteilen Teilsequenzen, und jede Teilsequenz ist geordnet. Fügen Sie dann die geordneten Teilsequenzen zur geordneten Gesamtsequenz zusammen. Dieser Algorithmus ist eine sehr typische Anwendung der Divide-and-Conquer-Methode (Divide and Conquer).

Fügen Sie die geordneten Teilsequenzen zusammen, um eine vollständig geordnete Sequenz zu erhalten. Sortieren Sie also zuerst jede Teilsequenz und dann die Teilsequenzsegmente. Wenn zwei geordnete Listen zu einer geordneten Liste zusammengeführt werden, spricht man von einer 2-Wege-Zusammenführung.

Angenommen, wir haben eine unsortierte Sequenz, dann verwenden wir zuerst die Aufteilungsmethode, um die Sequenz in sortierte Teilsequenzen zu unterteilen, und verwenden dann die Zusammenführungsmethode, um die Teilsequenzen einzeln zu trennen. Die Sequenzen werden zu sortierten Sequenzen zusammengeführt. Der Prozess der Segmentierung und Zusammenführung ist in der Legende unten zu sehen.

Wie Sie auf dem Bild oben sehen können, teilen wir eine unsortierte Sequenz zunächst von der Mitte aus in zwei Teile und teilen dann die 2 Teile in Teilen Sie es in 4 Teile und teilen Sie es nacheinander auf, bis es nacheinander in Daten unterteilt ist. Führen Sie diese Daten dann zusammen, um sie zu ordnen, führen Sie die Zusammenführung fort und bilden Sie schließlich eine geordnete Sequenz.

Wie füge ich zwei sortierte Teilsequenzen zu einer sortierten Sequenz zusammen? Sie können sich auf die folgende Methode beziehen.

Angenommen, wir haben zwei sortierte Teilsequenzen.

Sequenz A: 1 23 34 65

Sequenz B: 2 13 14 87

Dann können Sie die folgenden Schritte ausführen, um sie zu einer Sequenz zusammenzuführen.

(1) Stellen Sie zunächst eine neue Sequenz C[8] ein.
(2) Vergleiche A[0] und B[0], A[0] = 1, B[0] = 2, A[0] (3) Vergleich von A[1] und B[0], A[1] = 23, B[0] = 2, A[1] > B[0], dann C[1] = 2
(4) Vergleich von A[1] und B[1], A[1] = 23, B[1] = 13, A[1] > B[1], dann C[2] = 13
(5) Vergleich von A[1] und B[2], A[1] = 23, B[2] = 14, A[1] > B[2], dann C[3] = 14
( 6) Vergleich von A[1] und B[3], A[1] = 23, B[3] = 87, A[1] (7 ) Vergleicht man A[2] und B[3], A[2] = 34, B[3] = 87, A[2] (8) Vergleicht man A[3] und B[3], A[3] = 65, B[3] = 87, A[3] (9) Schließlich Kopieren Sie B[3] nach C, dann ist C[7] = 87. Die Zusammenführung ist abgeschlossen.

C#-Verschiebungsoperation (Linksverschiebung und Rechtsverschiebung)

Merge sort, The Die Zeitkomplexität beträgt O(nlogn).

Die Effizienz der Zusammenführungssortierung ist relativ hoch. Es werden logN-Schritte benötigt, um die Sequenz in Dezimalsequenzen aufzuteilen. Die Zeitkomplexität kann sein als O(N) aufgezeichnet werden, sodass die Gesamtsumme O(N*logN) ist. Da die Zusammenführungssortierung jedes Mal auf benachbarte Daten angewendet wird, sind mehrere Sortiermethoden der Zusammenführungssortierung (Schnellsortierung, Zusammenführungssortierung, Hill-Sortierung, Heap-Sortierung) in O(N*logN) ebenfalls relativ effizient.

Das Obige ist der Inhalt der C#-Zusammenführungssortierung. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn)!