Was bedeutet Zusammenführungssortierung?

Merge Sort ist ein effektiver Sortieralgorithmus, der auf der Merge-Operation basiert. Er führt geordnete Teilsequenzen zusammen, um eine vollständig geordnete Sequenz zu erhalten. Die Zusammenführungsoperation, auch Zusammenführungsalgorithmus genannt, bezieht sich auf die Methode zum Zusammenführen zweier aufeinanderfolgender Sequenzen zu einer einzigen sequentiellen Sequenz.

Zusammenführungssortierung (MERGE-SORT) ist ein effektiver Sortieralgorithmus, der auf Zusammenführungsoperationen basiert. Der Algorithmus verwendet die Divide-and-Conquer-Methode (Divide and Conquer). ) ist eine sehr typische Anwendung.

Fügen Sie die geordneten Teilsequenzen zusammen, um eine vollständig geordnete Sequenz zu erhalten, dh sortieren Sie zuerst jede Teilsequenz und dann die Teilsequenzsegmente.

Wenn zwei geordnete Listen zu einer geordneten Liste zusammengeführt werden, spricht man von einer bidirektionalen Zusammenführung. Die Zusammenführungssortierung ist eine stabile Sortiermethode.

Der Zusammenführungsvorgang (Merge), auch Zusammenführungsalgorithmus genannt, bezieht sich auf die Methode zum Zusammenführen zweier aufeinanderfolgender Sequenzen zu einer sequentiellen Sequenz.

Beispiel

Es gibt eine Sequenz {6, 202, 100, 301, 38, 8, 1}

Anfangszustand: 6,202,100,301,38,8, 1

Nach der ersten Zusammenführung: {6,202}, {100,301}, {8,38}, {1}, Anzahl der Vergleiche: 3;

Nach der zweiten Zusammenführung: {6,100,202,301} , {1,8,38}, Anzahl der Vergleiche: 4;

Nach der dritten Zusammenführung: {1,6,8,38,100,202,301}, Anzahl der Vergleiche: 4; Die Anzahl beträgt: 3+4+4=11;

Die umgekehrte Zahl ist 14;

Weitere Informationen zu diesem Thema finden Sie auf der

PHP-Website für Chinesisch

! !

Das obige ist der detaillierte Inhalt vonWas bedeutet Zusammenführungssortierung?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!