Heim Java javaLernprogramm Ausführliche Erläuterung von Beispielen für die Zusammenführungssortierung (nicht rekursiv) der Java-Vergleichssortierung

Ausführliche Erläuterung von Beispielen für die Zusammenführungssortierung (nicht rekursiv) der Java-Vergleichssortierung

Jun 28, 2017 pm 12:32 PM
排序 比较 递归

Im vorherigen Abschnitt haben wir die rekursive Version der Zusammenführungssortierung erklärt: „4. Vergleichende Sortierung – Zusammenführungssortierung (rekursiv)“. rekursive Version der Merge-Sortierung. Die Idee ist die gleiche wie bei der rekursiven Version, bei der zuerst zerlegt und dann zusammengeführt wird. Der Schwerpunkt der Nicht-Rekursion liegt auf der Bestimmung und sinnvollen Zerlegung des zu sortierenden Arrays.

Bei Nicht-Rekursion erfolgt die Segmentierung nicht von groß nach klein in Rekursionsrichtung. Bei Nicht-Rekursion beginnt die Segmentierung tatsächlich von klein nach groß, wenn der Algorithmus von Anfang an erstellt wird.

Bestimmen Sie beim ersten Segmentieren und Sortieren, dass die Mindesteinheit 1 Zahl ist, und kombinieren Sie 2 Zahlen zu einer Gruppe.

package com.algorithm.sort.mergenonrecursive;
import java.util.Arrays;
/**
 * 归并排序(非递归)
 * Created by yulinfeng on 2017/6/24.
 */
public class Merge {
    public static void main(String[] args) {
        int[] nums = {6, 5, 3, 1, 7, 2, 4};
        nums = mergeSort(nums);
        System.out.println(Arrays.toString(nums));
    }
    /**
     * 归并排序(非递归)
     * 从切分的数组长度为1开始,一次归并变回原来长度的2倍
     * @param nums 待排序数组
     * @return 排好序的数组
     */
    private static int[] mergeSort(int[] nums) {
        int len = 1;
        while (len <= nums.length) {
            for (int i = 0; i + len <= nums.length; i += len * 2) {
                int low = i, mid = i + len - 1, high = i + 2 * len - 1;
                if (high > nums.length - 1) {
                    high = nums.length - 1; //整个待排序数组为奇数的情况
                }
                merge(nums, low, mid, high);
            }
            len *= 2;
        }
        return nums;
    }
    /**
     * 将切分的数组进行归并排序,同递归版
     * @param nums 带排序数组
     * @param low 左边数组第一个元素索引
     * @param mid 左边数组最后一个元素索引,mid + 1为右边数组第一个元素索引
     * @param high 右边数组最后一个元素索引
     */
    private static void merge(int[] nums, int low, int mid, int high) {
        int[] tmpArray = new int[nums.length];
        int rightIndex = mid + 1;
        int tmpIndex = low;
        int begin = low;
        while (low <= mid && rightIndex <= high) {
            if (nums[low] <= nums[rightIndex]) {
                tmpArray[tmpIndex++] = nums[low++];
            } else {
                tmpArray[tmpIndex++] = nums[rightIndex++];
            }
        }
        while (low <= mid) {
            tmpArray[tmpIndex++] = nums[low++];
        }
        while (rightIndex <= high) {
            tmpArray[tmpIndex++] = nums[rightIndex++];
        }
        while (begin <= high) {
            nums[begin] = tmpArray[begin++];
        }
    }
}
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung von Beispielen für die Zusammenführungssortierung (nicht rekursiv) der Java-Vergleichssortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

Video Face Swap

Video Face Swap

Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Rekursive Implementierung von C++-Funktionen: Gibt es eine Grenze für die Rekursionstiefe? Rekursive Implementierung von C++-Funktionen: Gibt es eine Grenze für die Rekursionstiefe? Apr 23, 2024 am 09:30 AM

Die Rekursionstiefe von C++-Funktionen ist begrenzt und das Überschreiten dieser Grenze führt zu einem Stapelüberlauffehler. Der Grenzwert variiert je nach System und Compiler, liegt aber meist zwischen 1.000 und 10.000. Zu den Lösungen gehören: 1. Tail-Rekursionsoptimierung; 2. Tail-Call;

Unterstützen C++-Lambda-Ausdrücke die Rekursion? Unterstützen C++-Lambda-Ausdrücke die Rekursion? Apr 17, 2024 pm 09:06 PM

Ja, C++-Lambda-Ausdrücke können die Rekursion mithilfe von std::function unterstützen: Verwenden Sie std::function, um einen Verweis auf einen Lambda-Ausdruck zu erfassen. Mit einer erfassten Referenz kann sich ein Lambda-Ausdruck rekursiv selbst aufrufen.

Rekursive Implementierung von C++-Funktionen: Vergleichende Analyse rekursiver und nichtrekursiver Algorithmen? Rekursive Implementierung von C++-Funktionen: Vergleichende Analyse rekursiver und nichtrekursiver Algorithmen? Apr 22, 2024 pm 03:18 PM

Der rekursive Algorithmus löst strukturierte Probleme durch den Selbstaufruf von Funktionen. Der Vorteil besteht darin, dass er einfach und leicht zu verstehen ist. Der Nachteil besteht jedoch darin, dass er weniger effizient ist und einen Stapelüberlauf verursachen kann Der Vorteil der Stapeldatenstruktur besteht darin, dass sie effizienter ist und einen Stapelüberlauf vermeidet. Der Nachteil besteht darin, dass der Code möglicherweise komplexer ist. Die Wahl zwischen rekursiv und nicht rekursiv hängt vom Problem und den spezifischen Einschränkungen der Implementierung ab.

TrendX Research Institute: Merlin Chain-Projektanalyse und ökologische Bestandsaufnahme TrendX Research Institute: Merlin Chain-Projektanalyse und ökologische Bestandsaufnahme Mar 24, 2024 am 09:01 AM

Laut Statistiken vom 2. März hat der Gesamt-TVL des Bitcoin-Zweitschichtnetzwerks MerlinChain 3 Milliarden US-Dollar erreicht. Darunter machten die ökologischen Bitcoin-Vermögenswerte 90,83 % aus, darunter BTC im Wert von 1,596 Milliarden US-Dollar und BRC-20-Vermögenswerte im Wert von 404 Millionen US-Dollar. Letzten Monat erreichte der Gesamt-TVL von MerlinChain innerhalb von 14 Tagen nach dem Start der Absteckaktivitäten 1,97 Milliarden US-Dollar und übertraf damit Blast, das im November letzten Jahres gestartet wurde und auch das jüngste und gleichermaßen auffälligste ist. Am 26. Februar überstieg der Gesamtwert der NFTs im MerlinChain-Ökosystem 420 Millionen US-Dollar und wurde damit neben Ethereum zum öffentlichen Kettenprojekt mit dem höchsten NFT-Marktwert. Projekteinführung MerlinChain ist eine OKX-Unterstützung

Detaillierte Erläuterung der C++-Funktionsrekursion: Anwendung der Rekursion bei der Zeichenfolgenverarbeitung Detaillierte Erläuterung der C++-Funktionsrekursion: Anwendung der Rekursion bei der Zeichenfolgenverarbeitung Apr 30, 2024 am 10:30 AM

Eine rekursive Funktion ist eine Technik, die sich selbst wiederholt aufruft, um ein Problem bei der Zeichenfolgenverarbeitung zu lösen. Es erfordert eine Beendigungsbedingung, um eine unendliche Rekursion zu verhindern. Rekursion wird häufig bei Operationen wie der String-Umkehr und der Palindromprüfung verwendet.

C++-Rekursion für Fortgeschrittene: Grundlegendes zur Tail-Rekursionsoptimierung und ihrer Anwendung C++-Rekursion für Fortgeschrittene: Grundlegendes zur Tail-Rekursionsoptimierung und ihrer Anwendung Apr 30, 2024 am 10:45 AM

Tail Recursion Optimization (TRO) verbessert die Effizienz bestimmter rekursiver Aufrufe. Es wandelt endrekursive Aufrufe in Sprunganweisungen um und speichert den Kontextstatus in Registern statt auf dem Stapel, wodurch zusätzliche Aufrufe und Rückgabeoperationen an den Stapel entfallen und die Effizienz des Algorithmus verbessert wird. Mit TRO können wir tail-rekursive Funktionen (z. B. faktorielle Berechnungen) optimieren. Indem wir den tail-rekursiven Aufruf durch eine goto-Anweisung ersetzen, konvertiert der Compiler den goto-Sprung in TRO und optimiert die Ausführung des rekursiven Algorithmus.

Detaillierte Erläuterung der C++-Funktionsrekursion: Optimierung der Schwanzrekursion Detaillierte Erläuterung der C++-Funktionsrekursion: Optimierung der Schwanzrekursion May 03, 2024 pm 04:42 PM

Rekursive Definition und Optimierung: Rekursiv: Eine Funktion ruft sich intern auf, um schwierige Probleme zu lösen, die in kleinere Teilprobleme zerlegt werden können. Schwanzrekursion: Die Funktion führt alle Berechnungen durch, bevor sie einen rekursiven Aufruf durchführt, der in eine Schleife optimiert werden kann. Optimierungsbedingung für die Schwanzrekursion: Der rekursive Aufruf ist die letzte Operation. Die rekursiven Aufrufparameter sind dieselben wie die ursprünglichen Aufrufparameter. Praktisches Beispiel: Fakultät berechnen: Die Hilfsfunktion Factorial_helper implementiert die Schwanzrekursionsoptimierung, eliminiert den Aufrufstapel und verbessert die Effizienz. Fibonacci-Zahlen berechnen: Die Schwanzrekursivfunktion fibonacci_helper nutzt die Optimierung, um Fibonacci-Zahlen effizient zu berechnen.

Ein Anfängerleitfaden zur C++-Rekursion: Grundlagen schaffen und Intuition entwickeln Ein Anfängerleitfaden zur C++-Rekursion: Grundlagen schaffen und Intuition entwickeln May 01, 2024 pm 05:36 PM

Rekursion ist eine leistungsstarke Technik, die es einer Funktion ermöglicht, sich selbst aufzurufen, um ein Problem zu lösen. In C++ besteht eine rekursive Funktion aus zwei Schlüsselelementen: dem Basisfall (der bestimmt, wann die Rekursion stoppt) und dem rekursiven Aufruf (der das Problem aufteilt). kleinere Teilprobleme). Indem Sie die Grundlagen verstehen und praktische Beispiele wie faktorielle Berechnungen, Fibonacci-Folgen und binäre Baumdurchläufe üben, können Sie Ihre rekursive Intuition entwickeln und sie sicher in Ihrem Code verwenden.

See all articles