C#-Einfügungssortierung

C#, Einfügungssortierung

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
namespace Sort  
{  
    class InsertSorter  
    {  
        public static int[] Sort(int[] a)  
        {  
            InsertSort(a);  
            return a;  
        }  
        private static void InsertSort(int[] myArray)  
        {  
           int i, j,temp;            for (i = 1; i < myArray.Length; i++)  
            {  
                temp = myArray[i];//保存当前数据，当前数据即待插入的数据          
                //将数组标号i及i之前的元素，排成递增序列  
                for (j = i - 1; j >= 0 && myArray[j] >temp; j--)  
                {  
                    myArray[j + 1] = myArray[j];                 
                }  
                myArray[j + 1] = temp;  
            }  
     }  
  
    }  
}

Beispiel 1:

Schlüsselwortsequenz T=(13, 6, 3, 31, 9, 27 , 5, 11) Bitte schreiben Sie die Zwischenprozesssequenz der Direkteinfügungssortierung.

【13】, 6, 3, 31, 9, 27, 5, 11

【6, 13】, 3, 31, 9, 27, 5, 11

【3, 6, 13】, 31, 9, 27, 5, 11

【3, 6, 13, 31】, 9, 27, 5, 11

【3 , 6, 9, 13, 31】, 27, 5, 11

【3, 6, 9, 13, 27, 31】, 5, 11

【3, 5, 6 , 9, 13, 27, 31】, 11

【3, 5, 6, 9, 11, 13, 27, 31】

Kleiner Hinweis: Es ist jeweils nur das Array angeordnet kleine Schleife Die Reihenfolge dieser Elemente von 0 bis i (ähnlich wie beim Sprudeln)

Beispiel 2:

Beispiel 3:

Beim Einfügen des zweiten Elements muss das vorherige Element berücksichtigt werden Element, das vorherige Element muss berücksichtigt werden,..., um das N-te Element einzufügen, müssen die ersten N - 1 Elemente berücksichtigt werden. Daher beträgt die Anzahl der Vergleiche im schlimmsten Fall 1 + 2 + 3 + ... + (N - 1), und die arithmetische Folge wird summiert, und das Ergebnis ist N ^ 2 / 2, also die Komplexität im schlimmsten Fall Fall ist O (N^2).

Im besten Fall ist das Array bereits geordnet. Jedes Mal, wenn ein Element eingefügt wird, muss nur das vorherige Element untersucht werden. Daher beträgt die Zeitkomplexität der Einfügesortierung im besten Fall O(N). ).

Die Platzkomplexität der Einfügungssortierung beträgt O(1), da Sie während der Einfügungssortierung nur zusätzlichen Platz zum Speichern des „herausgenommenen“ Elements verwenden müssen, sodass die Einfügungssortierung nur zusätzlichen A-Platz zum Sortieren benötigt .

Space Complexity ist ein Maß für die Menge an Speicherplatz, die ein Algorithmus während des Betriebs vorübergehend belegt.

Da das Array intern sortiert ist, kann die relative Reihenfolge unverändert beibehalten werden, indem die folgenden Teile Stück für Stück verglichen und verschoben werden, sodass die Einfügungssortierung ein stabiler Sortieralgorithmus ist.

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