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 Artikel -Tags

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

Rekursive Implementierung von C++-Funktionen: Gibt es eine Grenze für die Rekursionstiefe?

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

Unterstützen C++-Lambda-Ausdrücke die Rekursion?

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

Rekursive Implementierung von C++-Funktionen: Vergleichende Analyse rekursiver und nichtrekursiver Algorithmen?

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

Detaillierte Erläuterung der C++-Funktionsrekursion: Anwendung der Rekursion bei der Zeichenfolgenverarbeitung

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

Ein Anfängerleitfaden zur C++-Rekursion: Grundlagen schaffen und Intuition entwickeln

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

TrendX Research Institute: Merlin Chain-Projektanalyse und ökologische Bestandsaufnahme

Erweiterte Sortierung von PHP-Arrays: benutzerdefinierte Komparatoren und anonyme Funktionen Erweiterte Sortierung von PHP-Arrays: benutzerdefinierte Komparatoren und anonyme Funktionen Apr 27, 2024 am 11:09 AM

Erweiterte Sortierung von PHP-Arrays: benutzerdefinierte Komparatoren und anonyme Funktionen

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

C++-Rekursion für Fortgeschrittene: Grundlegendes zur Tail-Rekursionsoptimierung und ihrer Anwendung

See all articles